theory - 下推自动机

Question

为语言 a^nbc^n+2, n>0 设计下推自动机我被要求为上述语言实现自动机..请帮忙？

每次我将 (a) 压入堆栈时，我都尝试弹出 2 (c)s，但它似乎不适用于奇数个 (a)s ....

Answer 1

您必须以正常方式处理a，即每个从您堆叠A的磁带中读取，直到您完成读取a，如果您读取ab，则保持堆栈顶部不变，最后您必须处理所有CS。转换函数为：

(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 的图形表示为：