Thanks! I read the wikipeida article and discovered the charming programming language Thue
I have yet another CFG question. This one's a bit more mathematical.
I had the realization that CFGs are essentially a class of directed hypergraphs and parse trees are in a sense a "walks" on them. Furthermore, it should be possible to create a 3 dimensional adjacency matrix that represents any CFG in Chomsky normal form.
So, what I'm wondering about is what kind of properties this mathematical formulation has that would be of interest in relation to the CFGs it represents. For example, adjacency matrices for standard digraphs can tell us a number of things. Their determinate can indicate if they are NOT isomorphic, and finding a permutation matrix between them can indicate they are. Their eigenvalues/vectors can be used to rank nodes. Another thing we are usually interested in for standard digraphs are minimum spanning trees and least cost paths/traversals. Do these have analogs for CFGs?
We might also be interested in whether a random walk on a graph returns to it's origin. What happens when the walk bifurcates?