如何n^n b^n其中n> = 1是不規則的？

Question

這是我試過的簡單有限自動機，我做錯了什麼？

Answer 1

b轉換導致終止狀態，終止機器。如果給定的長度爲1或更長的「ab」序列，您的機器只會停止。

Answer 2

這匹配，而不是。又名ababab，而不是aaabbb。

Answer 3

語言a^n b^n其中n> = 1不規則，可以用抽象引理證明。假設有一個可以接受語言的有限狀態自動機。這個有限自動機的狀態數k是有限的，並且在語言中有字符串x使得n> k。根據抽象引理，x可以被分解成x = uvw，並且任何接受x的有限自動機也必須接受uv * w。 v是非空的，並且由於n> k，所以可以使其僅由a或b組成。讓v僅由a組成。如果有限自動機接受x = uvw，它也必須接受x = uvvw，它具有比b更多的a，而不是形式a^n b^n。這是一個矛盾，所以a^n b^n不能成爲常規語言。

Answer 4

這匹配（ab）^ n，而不是^ nb^n。

什麼你要找的是Pumping lemma for regular languages.

例子：
令L = {a^MB^M | m≥1}。
然後L不規則。證明：設n爲Pumping引理。
令w = a^nb^n。設w = xyz爲抽樣引理。
因此，xy ^2z∈L，但是，xy^2z包含比b更多的a。