Как построить NPDA, соответствующий приведенной ниже грамматике?

Question

Я хочу построить NPDA, соответствующий приведенной ниже грамматике. Пожалуйста, скажите мне идею строительства.

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

Answer 1

Общий метод получения NPDA из CFG заключается в следующем:

1. Преобразование грамматики G в нормальную форму Хомского (CNF); вызовите получившуюся грамматику G '.
2. Переведите NPDA pu sh начальный символ G в стек и перейдите во второе состояние.
3. В этом втором состоянии возможны два случая :
   • Если символ стека является нетерминалом в 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, который принимает.