Chr*_*man 14 computer-science fsm regular-language
在我接受的CS课程中,有一个不常规的语言示例:
{a^nb^n | n >= 0}
我可以理解它不常规,因为没有有限状态自动机/机器可以编写验证和接受此输入,因为它缺少一个内存组件.(如果我错了,请纠正我)
关于常规语言的维基百科条目也列出了这个例子,但没有提供(数学)证明为什么它不常规.
任何人都可以启发我并为此提供证据,或者指出我太好的资源？
cle*_*tus 14
您正在寻找的是常规语言的抽取引理.
以下是您确切问题的示例:
例子:
设L = {a m b m | m≥1}.
然后L不规律.
证明:让我像泵浦引理一样.
设w = a n b n.
设w = xyz与泵浦引理相同.
因此,XY 2 Z∈L,但是,XY 2 Z含有更多的比B的.
因为你不能编写一个有限状态机来"计算"'a'和'b'符号的相同序列.简而言之,FSM无法"计算".尝试想象这样一个FSM:你会给符号'a'多少个州？'b'有多少？如果输入序列有更多,该怎么办？
请注意,如果n <= X且X为整数值,则可以准备这样的FSM(通过使其具有大量状态,但仍然是有限数); 这种语言会定期.
小智 5
原因是，只有在“否”时才必须达到最终状态。'a' 和没有。'b' 在输入字符串中相等。要做到这一点，你必须同时计算两个，即“否”。'a' 以及 no。'b' 的值，但由于 'n' 的值可以达到无穷大，因此使用有限自动机不可能计数到无穷大。
这就是为什么 {a^nb^n | n >= 0} 不规则。