1

我如何证明这种语言是否正常？

L = {a n b n : n≥1} 并集 {a n b n+2 : n≥1}

4

2 回答 2

1

我将给出一个方法和一个证明的草图，其中可能有一些漏洞，我相信你可以填补自己。

这个想法是使用nerode 的定理- 证明 R L有无限个等价群- 从定理你可以得出语言是不规则的。

定义两种类型的集合：

  1. G_j = {a n b k | nk = j , k≥1} 对于 [-2,-1,0,1,...] 中的每个 j
  2. H_j = {a j } 对于 [0,1,...] 中的每个 j
  3. G_illegal = {0,1} * / (G_j U H_j) [对于指定范围内的每个j]

很容易看出 for each xinG_illegal和 for each zin {a,b} * :xz不在L.

因此，对于每个x,y inG_illegal和对于每个zin {a,b} * : xzin L<-> yzin L。

此外，对于z{a,b} *中的 each - 以及对于 each x，y在某些G_j[j两者相同] 中：

  • 如果z包含，a则两者都在xzyzL
  • 如果z= b j，则 xz = a n b k b j，并且因为k+j = n-xz在L. 同样适用于y，yz在 中也是如此L。
  • 如果z= b j+2，则 xz = a n b k b j+2，并且因为k+j+2 = n+2-xz在L. 同样适用于y，yz在 中也是如此L。
  • 否则，x是 b i使得 i≠j 和 i≠j+2，并且你得到两者xz并且yz不在L.

因此，对于每个 j 和对于每个x,yinG_j以及对于z{a,b} *中的每个：xz在L<-> yzin 中L。

证明每个H_j使用相同方法的相同。

此外，很容易证明，对于每个xG_j U H_j 和 G_illegal 中的每个y- for z= b j，xz 在 L 中而 yz 不在 L 中。
对于xG_j 和yH_i，对于 z = ab j+ 1 - 很容易看出xz不在L和yz在L。
很容易看出 for x,y在 G_j 和 G_i 中分别或x,y在 H_j 中, H_i - for z= b j : xzis in Lwhile yzis not。

我们刚刚证明了我们创建的集合实际上是来自nerode 定理的 R L的等价关系，并且由于我们有无限数量的这些集合，每个都是 R L的等价关系[我们有并且对于每个] -我们可以从nerode 的定理，即语言是不规则的。H_jG_jjL

于 2012-03-22T22:59:34.767 回答
0

您可以将抽水引理用于常规语言。它基本上是说，如果你能找到任何给定整数 n 的字符串，并且该字符串的任何分区为 xyz 使得 |xy| <= n, 和 |y| > 0，那么你可以抽出字符串的 y 部分，它必须保持在语言中，这意味着，如果 xy^iz 它不是某些 i 的语言，那么该语言是不规则的。

证明是这样的，一种对抗性证明。假设有人告诉您这种语言是常规语言。然后问他一个 n > 0 的数字。你建立一个长度大于 n 的方便字符串，然后给对手。他以任何他想要的方式将字符串划分为 x, yz，只要 |xy| <= n。然后你必须抽 y （重复 i 次），直到你找到一个不是同一种语言的字符串。

在这种情况下，我告诉你：给我 n。你修复n。我告诉你：取字符串“a^nb^{n+2}”，然后告诉你拆分它。无论如何，你可以分割这个字符串，你总是必须使 y = a^k，k > 0，因为你被迫使 |xy| <= n，我的字符串以 a^n 开头。这是诀窍，你给对手一根绳子，这样他就可以用任何方式分割它，他给你一个你可以抽的部分。所以现在我们抽 y，比方说 0 次，你得到 m < n 的“a^mb^{n+2}”，这不是你的语言。完毕。我们也可以抽1次，n次，n！阶乘，任何你需要让它离开语言的东西。

这个定理的证明到处都是说，如果你有一种常规语言，那么你就有一个具有 n 个状态的自动机，用于某个固定的 n。如果一个字符串有超过 n 个字符，那么它必须在你的自动机中经历一些循环。如果我们将 x 命名为进入循环之前的字符串部分，将 y 命名为循环中的部分，很明显我们可以将 y 泵入任意次数，因为我们可以在循环中继续运行任意多次，并且生成的字符串必须使用该语言，因为它将被该自动机识别。要使用该定理来证明非正则性，由于我们不知道假定的自动机将如何，我们必须让对手选择 n 和自动机内循环的位置（不会有自动机，但你对对手说：

于 2012-04-04T20:55:57.160 回答