context-free-grammar - 设计一个下推自动机来计算字符数

Question

字母：a、b、c 我正在尝试定义一个接受

 a^n b^m c^p : n + p = 2k for some integer k, m = k, and n, m, p, k >= 0

我认为可以接受的一些字符串是：#abc#; #aabbcc#; #aaabbbccc#; #abbccc#; #aaabbc# 等 a、b 和 c 的数量不一定相等。

在最右边的黑色空间上启动下推自动机的头部。

通常我把我的 PDA 写成列：

State:    Symbol Read:    Next State:    Head Instruction:    
s         #               r1             Left
r1        c               r2             #

等等...

Answer 1

我认为您描述的语言不是上下文无关的，因此无法用 PDA 识别。问题是您需要强制执行一个跨越任意长子字符串的约束（n+p = 2m），但不允许“泵送”（当尝试使用无上下文语言的泵送引理构造证明时）。

Answer 2

M=(K, E, q0, F, delta, stack_alphabet)
K={q0,q1,q2}
E={a,b,c,z}
F={q2}
stack_alphabet={a,b,z}
delta=
{
 *pop*     *push*
(q0, e, e)(q1, z)
(q1, a, e)(q1, a)
(q1, b, a)(q1, e)
(q1, b, z)(q1, bz)
(q1, c, b)(q2, e)
(q2, c, b)(q2, e)
}