finite-automata - 我怎样才能证明这种语言是正规的？

Question

我正在尝试证明这种语言是否:

L = { w={0,1}* | #₀(w) % 3 = 0 } (number of 0's is divisble by 3)

经常使用抽水引理，但我找不到办法。我得到的所有其他示例，有一个简单的形式，或者说一个更定义的形式，例如 w = a^xb^yc^z 等。

Answer 1

我认为您不能使用抽引引理来证明一种语言是正则的。要证明一种语言是正则的，你只需要给出一个正则表达式或一个 DFA。在这种情况下，正则表达式非常简单:

1*(01*01*01*)*

(证明:正则表达式显然不接受任何0个数不能被3整除的字符串，所以我们只需要证明所有可能的0个数能被3整除的字符串都被这个正则接受表达式，可以通过确认对于包含 3n 个 0 的字符串，正则表达式匹配它，因为 1^n₀01^n₁01^n₂01^n₃...01^n_3n-201^n_3n-101^n_3n 有可以替换相同数量的 0 和 n_k，使其与字符串匹配，并且正则表达式清楚地接受这种格式)

Pumping lemma 不能用来证明一种语言是正则的，因为我们不能像 Daniel Martin 的回答那样设置 y 。这是一个反例，格式与他的答案相似(如果我做的事情与他的答案完全不同，请纠正我):

We prove that the language L = {w=0ⁿ1^p | n ∈ N, n>0, p is prime} is regular using pumping lemma as follows: note that there is at least one occurrence of 0, so we take y as 0, and we have xy^kz = 0^n+k-11^p, which still satisfy the language definition. Therefore L is regular.

但这是错误的，因为我们知 Prop 有素数长度的序列是不规则的。这里的问题是我们不能只将 y 设置为任何字符。