0

我应该如何L={a^n b^m | n=km for k in N}使用抽水引理证明这不是常规语言？

我从输入一个词w开始L，w=a^n b^m用n=km一些k输入N。有三种可能的分解w：

  1. a^i * a^j * a^(n-i-j) b^m
  2. a^i * a^(n-i) b^j * b^(m-j)
  3. a^n b^i * b^j * b^(m-i-j)

抽点 2) 的中间部分会导致混淆的词，这显然不是 in L，但我不明白为什么 1) 不能给你一个很好的分解：

假设你抽水a^j x时间。那么新单词中 a 的数量将是i+xj+n-i-j = n+(x-1)j。我们知道n=km一些m。我们必须证明存在一个x这样的新词不在L. 但是让我们假设j=m（这当然是可能的，因为n=km总是有足够数量的 a，除非当k=0，但是我们得到一个微不足道的情况）。然后n+(x-1)j = km+(x-1)m = m(n+x-1)which 是{a^n b^m | n=km for k in N}all的形式x。所以对于每一个w我们都有一个分解uvz，这样u v^i z就L适用于所有i。因此，由抽引理，L是正则的。

我错过了什么？

编辑：给出的泵送引理的公式：

让L成为带有k状态的 DFA 接受的常规语言。让w任何单词 in Lwith length >= k。然后w可以写成u v zwith |uv| <=k, v>0and u v^i zin Lfor alli>=0

4

1 回答 1

1

证明这一点的一种可能更简单的方法是首先修改语言。

由于正则语言在补码和与另一个正则表达式的交集下是封闭的。

这意味着你可以L通过证明不是正则语言来证明complement(L)不是正则语言，因为如果L'是正则语言，L反之亦然。交叉口也是如此。

证明L'也不是正则就足够了：

L' = intersection(complement(L),a*b*})

因此

L'={a^nb^m|n != k*m, for any k in N}

然后证明变得更容易，因为你可以展示你用作抽引引理的任何部分，如果它有 length l，你可以抽它足够的次数来达到倍数。

于 2015-01-05T11:47:29.987 回答