文脈自由文法の記法は、自己言及的に記述すると以下のように書ける筈です。
CFG → pattern CFG
CFG → pattern
pattern → NTE "→" rightside
rightside → NTE
rightside → TE
rightside → NTE rightside
rightside → TE rightside
NTE → ident
TE → string
この時、identは変数を表す文字列、stringは文字列を表す文字列とします。上記の略称はそれぞれ、
CFG = Context Free Grammer = 文脈自由文法、
NTE = None Terminal Expression = 非終端記号、
TE = Terminal Expression = 終端記号です。
こう書ける筈なんだけど、実際にこんな定義は、教科書でもネットでも見たことない。間違ってるのかな? それとも、あまりに下らないので、誰も書かないだけなんだろうか、とか思って、Wikipediaとか読んで、思い出してたのですが。
文脈自由文法の形式的な定義は、
G = (V, Σ, R, S)のタプルで、
Vは、非終端記号の有限集合
Σは、終端記号の有限集合
Rは、生成規則の集合
Sは、開始記号(生成される木構造のトップ)
で表されるんだそうです。
そこで、生成規則の定義なのですが、
v → w
で、定義されて、v∈V, w∈(V∪Σ)*で表されるのだそうです。あっさりしてますね。
確かにこれと比べたら、冒頭の定義は、無駄に長ったらしいです。
ただ、文脈自由文法が文脈自由文法で表せるなら、プッシュダウンオートマトン上に別のプッシュダウンオートマトンが作れるってことでしょうか。なんだかチューリングマシンみたいで、面白いですね。