我想构造与以下语法相对应的 NPDA。 请告诉我构建的想法。
S -> aABB|aAA
A -> aBB|a
B -> bBB|A
最佳答案
从 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 接受。
关于computer-science - 如何构造对应于以下语法的NPDA?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60049422/