12

我在解决/证明这个问题时遇到了麻烦。请问有什么想法吗？

4

1 回答 1

16

L = {a n b m | n > m}不是 常规语言。

是的，这个问题在最初的几次尝试中很棘手，值得投票。

抽取引理是常规语言的必要属性，是正式证明语言不是常规语言的工具。

正式定义：为常规语言抽取引理

令L为常规语言。那么存在一个整数p ≥ 1 仅取决于L使得L中长度至少为p的每个字符串 w（p称为“泵送长度”）可以写成w = xyz（即w可以分为三个子字符串），满足以下条件：

  1. | 是| ≥1
  2. | xy | ≤ p
  3. 对于所有 i ≥ 0，xy i z ∈ L

假设，如果你选择字符串W = a n b m where (n + m) ≥ pand n > m + 1。W的选择是有效的，但是这个选择你不能证明语言不是常规语言。因为有了这个W，你总是至少有一个选择，y=a通过重复 (for i =0 and i > 1) 的所有值来抽取a新的语言字符串i 。

在我写我的解决方案来证明语言不规则之前。请理解以下几点和注意：我在上面对泵引理做了粗体every string w和all i正式的定义。

  • 尽管在语言中使用 Some Sufficiently large W时，您可以在 Language 中生成新字符串，但不可能使用 ALL！W有很多可能的选择（在我的证明中），您找不到任何选择y来为所有 i >=0生成语言中的新字符串。因此，因为每个足够大的W都无法在语言中生成新字符串，因此语言不是常规的。

阅读：什么泵引理正式定义说

证明：使用抽水引理

步骤（1）：选择字符串W = a n b m where (n + m) ≥ pand n = m + 1。

Is this choice of W is valid according to pumping lemma?

是的，这样的W在语言中是因为 number of a= n > number of b=m 。W在语言中并且足够大 >= p。

步骤（2）：现在选择 ay为all i >= 0生成新字符串。

而这一次是没有选择的余地y！为什么？

首先，要理解我们不能在yb中包含符号，因为它会生成不符合模式的新字符串，或者生成的字符串总数将超过符号总数。 ba

其次，我们不能选择y = some a 's因为i=0你会得到一个新字符串，其中as 的数量将小于数字bs，这在语言中是不可能的。（记住aW 中的数量只是多一个b因此删除结果字符串 N(a)=N(b) 中不可接受的任何 a 手段，因为 n>m )

因此，我们可以找到一些足够大的 W，但是使用它我们无法生成与常规语言的泵引理属性相矛盾的语言中的新字符串，因此语言 {a n b m | n > m} 确实不是常规语言。

于 2013-03-03T10:33:53.660 回答