[解決済み] 以下の文法に対応するNPDAはどのように構築するのか？

質問

以下の文法に対応するNPDAを構築したい。 どのような考え方で構築するのか教えてください。

S -> aABB|aAA
A -> aBB|a
B -> bBB|A

解決方法は？

CFGからNPDAを取り出す一般的な方法は以下の通りです。

1. 文法Gをチョムスキー正規形（CNF）に変換し、できた文法をG'と呼ぶ。
2. NPDAにGの開始記号S'をスタックに押させ、第2の状態に遷移させる。
3. この第2の状態において、2つのケースがある。
   • スタック記号がG'の非終端である場合、G'のその非終端に対するプロダクションの一つを非決定的に選択し、非終端をそのプロダクションの右辺に置き換えた場合
   • スタック記号がG'の端末である場合、その端末記号をNPDAで消費し、スタックから単純にポップオフする

つまり、私たちのNPDAは次のようになります。

states: q0, q1
alphabet: a, b
stack alphabet: Z, a, b, S, A, B
start state: q0
final state: q1
transitions:

    (q0, e, Z) -> (q1, SZ)
    (q1, e, S) -> (q1, aABB)
    (q1, e, S) -> (q1, aAA)
    (q1, e, A) -> (q1, aBB)
    (q1, e, A) -> (q1, a)
    (q1, e, B) -> (q1, bBB)
    (q1, e, B) -> (q1, A)
    (q1, a, a) -> (q1, e)
    (q1, b, b) -> (q1, e)

以下は、文字列aaaaを処理する実行トレースです。

state: q0, stack: Z     , remaining input: aaaa
state: q1, stack: SZ    , remaining input: aaaa
state: q1, stack: aABBZ , remaining input: aaaa
state: q1, stack: ABBZ  , remaining input: aaa
state: q1, stack: aBBZ  , remaining input: aaa
state: q1, stack: BBZ   , remaining input: aa
state: q1, stack: ABZ   , remaining input: aa
state: q1, stack: aBZ   , remaining input: aa
state: q1, stack: BZ    , remaining input: a
state: q1, stack: AZ    , remaining input: a
state: q1, stack: aZ    , remaining input: a
state: q1, stack: Z     , remaining input: e

したがって、文字列aaaaは、受け入れるNPDAの経路が1つであるため、受け入れられます。