制作 PDA 以识别以下语言:a 多于 b 的字符串语言
我已经为这个问题苦苦挣扎了好几天了,我似乎已经完全陷入了精神障碍。任何人都可以为我如何解决这个问题提供一些指导或指导吗?
制作 PDA 以识别以下语言:a 多于 b 的字符串语言
我已经为这个问题苦苦挣扎了好几天了,我似乎已经完全陷入了精神障碍。任何人都可以为我如何解决这个问题提供一些指导或指导吗?
PDA 可以解决您“a 多于 b”的问题。
你所要做的就是:
当输入为a
且堆栈为空或a
顶部有一个时,推入a
堆栈;pop b
,如果b
是顶部。
当输入为b
且堆栈为空或b
顶部有一个时,推入b
堆栈;pop a
,如果a
在顶部。
a
最后,当字符串完成时,如果在堆栈顶部,则使用 null 输入进入最终状态。否则你没有a
比's 更多的b
's 。
我假设您的意思是形式的字符串a^nb^m
,其中n
> m
。
这个想法相对简单,因为a
你将它压入堆栈(在一个循环中),因为b
你切换到一个单独的循环以a
从堆栈中弹出。如果堆栈是空的,你放弃失败。如果在第一个循环中你得到除a
or以外的任何东西b
,或者在第二个循环中你得到除 之外的任何东西b
,你就放弃了 FAIL。
最后,您尝试弹出另一个a
,如果堆栈为空,您将放弃 FAIL(即,堆栈上的 ' 至少与b
'一样多a
,可能更多)。如果没有,成功。
编辑:作为旁注,我不相信这是解决这个问题的正确网站,可能对程序员更好。不确定,所以不投票关闭。