Type2 Language - formallang.memo

Type-2 Language / 文脈自由言語

文脈自由文法

<N,Σ,S,R>

• N : 非終端記号
• Σ : 終端記号
• S ∈ N : 開始記号
• R : A→α where α∈(N∪Σ)* の形の生成規則の集まり

プッシュダウンオートマトン

初出は

• "Context-free grammars and pushdown storage" (1962)
• Noam Chomsky
• Quarterly Progress Report 65, Research Laboratory of Electronics, Mass

らしい。

• "On Context-Free Languages and Push-Down Automata" (1963)
• M. P. Schützenberger
• Information and Control, vol. 6, pp. 246-264
• http://dx.doi.org/10.1016/S0019-9958(63)90306-1

オートマトン＋遷移時にスタックの先頭をpopできる＆＆複数のシンボルをpushできる。

性質(メモ)： いくつかの決定不能問題

• ２つの文脈自由言語が共通部分を持つかどうかは決定不能

証明: 決定不能問題として知られているPCP（ポストの対応問題 / Post Correspondence Problem）に帰着する。
　　 {w1,...,wn} と {u1,...,un} の PCPのマッチが存在する
　 　　 if and only if
　　 適当に{i1,...,in} という文字集合をとってきて
　　　 W->w1 W i1 | w1i1 | ... | wn W in | wn in
　　　 U->u1 U i1 | u1i1 | ... | un W in | un in
　　 のL(W)とL(U)の共通部分がある。
よって前者が決定不能なので後者も決定不能。

• 文脈自由文法が曖昧（2種類以上のparse方法がある場合がある）かどうかは決定不能

証明: 上のW,Uを使って Z -> W|U とすると PCPマッチがある iff Z が曖昧