如何构造对应于以下文法的NPDA？

Question

我想构造对应于下面语法的NPDA。请说说施工思路

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 接受。

如何构造对应于以下文法的NPDA？

How to construct NPDA corresponding to the below grammar?

computer-science

automata