下推自动机

Question

为语言a^n b c^n+2，n>0设计下推自动机我被要求实现上述语言的自动机。请帮帮忙？

我尝试在每次将(a)推送到堆栈时弹出2 (c)s，但似乎对奇数个(a)s不起作用。

Answer 1

你必须以正常的方式处理A，也就是说，对于每个从你堆叠的磁带中读取的a，直到你读完a，如果你读取了b，保持堆栈的顶部不变，最后你必须处理所有的C。转换函数是：

(q0, a, Z) = (q0, AZ)
(q0, a, A) = (q0, AA)
(q0, b, A) = (q1, A)
(q1, c, A) = (q1, epsilon) (until the amount of a's are equal to the amount of c's)
(q1, c, Z)= (q2, Z) (read the first extra c)
(q2, c, Z)= (q3, Z) (read the second extra c)
(q3, epsilon, Z)= (qf, Z) (qf is the final state)

PDA的图形表示为：

​

​