computer-science - 如何构造对应于以下语法的NPDA？

Question

我想构建对应于以下语法的 NPDA。
请告诉我 build 的想法。

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

Answer 1

从 CFG 中获取 NPDA 的一般方法如下:

将语法 G 转换为乔姆斯基范式 (CNF)；将结果文法称为 G'。

使 NPDA 将 G 的起始符号 S' 压入堆栈并转换到第二个状态。

在这第二种状态下，有两种情况:

如果堆栈符号是 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 的路径接受。