automata - n>=1 的 a^nb^n 如何不规则？

Question

这是我尝试过的简单有限自动机，我做错了什么？

Answer 1

这匹配，不是。阿卡ababab，不是aaabbb。

Answer 2

这匹配 (ab)^n，而不是 a^nb^n。

您正在寻找的是为常规语言抽取引理。

示例：
令 L = {a^mb^m | 米≥1}。
那么 L 不是正则的。
证明：令 n 与 Pumping Lemma 中的一样。
令 w = a^nb^n。
令 w = xyz 与 Pumping Lemma 中的一样。
因此，xy^2z ∈ L，然而，xy^2z 包含的 a 比 b 多。

Answer 3

b 转换导致停止机器的最终状态。只有在给定长度为 1 或更长的“ab”序列时，您的机器才会停止。

Answer 4

n>=1 的语言 a^nb^n 是不规则的，可以使用泵引理证明。假设有一个可以接受该语言的有限状态自动机。这个有限自动机具有有限数量的状态 k，并且语言中有字符串 x 使得 n > k。根据泵浦引理，x 可以分解为 x=uvw，并且任何接受 x 的有限自动机也必须接受 uv*w。v 是非空的，并且可以仅由 a 或 b 组成，因为 n > k。令 v 仅由 a 组成。如果有限自动机接受 x = uvw，它也必须接受 x = uvvw，它的 a 比 b 多，并且不是 a^nb^n 的形式。这是一个矛盾，所以 a^nb^n 不能是常规语言。