为以下语言设计PDA
L = {a ^ nb ^ m:m≥n,m-n是偶数}。
让我们从PDA开始,其中m> = n。 PDA可以为它看到的每一个a向一个堆栈推送一个b,为它看到的每一个b弹出一个b,如果它在堆栈中仍有一个b时用尽了b,它就会拒绝。
现在,我们还需要做些什么才能排除m-n为奇数的情况?好吧,m - n是奇数意味着我们在输入中剩下一些b。我们可以简单地修改我们的接受状态,以便在进一步的b上,它移动到新的状态(编码奇数b),然后返回到下一个b的接受状态,编码残差b必须是偶数的要求。
完整的PDA可能如下所示:
q s S q' S'
q0 a Z q0 aZ
q0 a ax q0 aax
q0 b Zx q2 Z
q0 b ax q1 x
q1 b ax q1 x
q1 b Z q2 Z
q2 b Z q1 Z
检查它是否有效,可能存在一些错误。阅读方式是:
从状态q,在输入s上,使用堆栈配置S,PDA可以转换到状态q'并将堆栈配置更新为S'。