PDA的L = {a ^ nb ^ m:m≥n,m-n是偶数}

问题描述 投票:0回答:1

为以下语言设计PDA

L = {a ^ nb ^ m:m≥n,m-n是偶数}。

automata pushdown-automaton
1个回答
0
投票

让我们从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'。

© www.soinside.com 2019 - 2024. All rights reserved.