なにやら難しい話が進行中っぽいけど、トピックそのものは面白そうなんで
まずは>>4なんかを考えてみたけど、どうっすか。

その前に、ノードにラベルをつけるってのは、構文解析前に字句要素を抽出するみたいなノリでＯＫ？
そんな感じで、迷路のスタートとゴールのノードをsとg、袋小路(dead end)をd、袋小路でない交差点(cross)をcと
いうのがすでにラベル付けされているとして、エッジを-で表して、迷路のグラフ文法Mを
M := s-X-g
X := X-Y
X := X-X
Y := Y-d
Y := c-d
ってのはどうよ。