0

我正在复习我的计算理论课程笔记，但我无法理解如何完成某个证明。这是问题：

A = {0^n 1^m 0^n | n>=1, m>=1}  Prove that A is not regular.

很明显，必须使用抽水引理。所以，我们有

  1. |维| >= 1
  2. |vxy| <= p (p 是泵送长度，>= 1)
  3. uv^ixy^iz 对于所有 i >= 0 都存在于 A 中

尝试考虑选择正确的字符串似乎有点不确定。我在想0^p 1^q 0^p，但我不知道我是否可以模糊地制作aq，而且由于你没有约束，这可能会让事情变得不守规矩..

那么，怎么办呢？

4

3 回答 3

4

如果您使用适用于常规语言的泵引理的定义，而不是适用于 CFG 的定义，它会简单得多。任何常规字符串 s = xyz 必须具备的三个条件是：

  1. 对于每个 i >= 0，xy^iz 在 A
  2. |是| >= 0
  3. |xy| <= p

使用这三个条件再次尝试使用 0^p1^q0^p。

提示：因为我们有 0^p，所以 y 将只包含 0。因此，当我们“输入”更多的 y（考虑 xyyz）时，我们将不会得到该语言中的字符串。

于 2010-04-11T17:24:36.413 回答
3

您使用了错误的抽水引理... A 在这里是无上下文的，但它不是常规的。

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

这应该向您展示您需要的引理......如果您从它开始，您可能会想出一个答案。如果没有，请告诉我，我会编辑我的答案给你一些提示。

于 2010-04-11T17:23:55.923 回答
0

我会在没有引理的情况下解决它： - 考虑 h​​(a) 其中 h(1)=1 h(2)=0 h(0)=0。将 h^-1 应用于您的语言，然后与 0^*1^ 2^相交，即可得到语言 0^n1^m2^n。- 现在使用 h'(a)，其中 h'(0)=a，h'(1)=epsilon，h'(2)=b。你得到 a^nb^n 这是不规则的。

为什么这更容易？因为在学习了这些基本技巧之后，您可以非常轻松地解决这个问题。

至于引理： - 当用作子字符串时，您将需要 A 中单词的任何子字符串会破坏您的语言。我可以看到 6 种情况（只有从一开始的 0，从一开始的 0，然后是 1，等等......）

正如其他已经添加的那样，您不需要 CF 引理。CF-lemma 通常用于表明一种语言不是 CF。

于 2010-04-11T17:38:42.160 回答