PDA接受包含比a多的a的字符串语言 [英] PDA to accept a language of strings containing more a's than b's

问题描述

使PDA识别以下语言:包含比a更大的a的字符串的语言.

Produce a PDA to recognise the following language : the language of strings containing more a's than b's

我已经为这个问题苦苦挣扎了好几天了，我似乎已经完全陷入了精神障碍.任何人都可以为我如何解决此问题提供一些指导或指导?

I have been struggling with this question for several days now, I seem to have hit a complete mental block. Would any one be able to provide some guidance or direction to how I can solve this problem?

推荐答案

您的"a大于b"的问题可以通过PDA解决.

Your problem of "more a's than b's" can be solved by PDA.

所有您需要做的是:

• 当输入为a且堆栈为空或顶部为a时，将a压入堆栈；如果b是顶部，则弹出b.

• When input is a and the stack is either empty or has an a on the top, push a on the stack; pop b, if b is the top.

当输入为b且堆栈为空或顶部为b时，将b推入堆栈；否则为0.如果a在顶部，则弹出a.

When input is b and the stack is either empty or has an b on the top, push b on the stack; pop a, if a is on the top.

最后，当字符串完成时，如果a位于堆栈顶部，则使用空输入进入最终状态.否则，您的a不能超过b的数量.

Finally, when the string is finished, go to the final state with null input if a is on top of the stack. Otherwise you don't have more a's than b's.

这篇关于PDA接受包含比a多的a的字符串语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！