文脈自由文法で文脈自由文法の記法を定義してみる。

文脈自由文法の記法は、自己言及的に記述すると以下のように書ける筈です。

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∪Σ)*で表されるのだそうです。あっさりしてますね。

　確かにこれと比べたら、冒頭の定義は、無駄に長ったらしいです。
　ただ、文脈自由文法が文脈自由文法で表せるなら、プッシュダウンオートマトン上に別のプッシュダウンオートマトンが作れるってことでしょうか。なんだかチューリングマシンみたいで、面白いですね。