是L = {a ^ nb ^ m | n> m}常规或不规则的语言？

Question

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

Answer 1

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

是的,这个问题在最初几次尝试时很棘手,值得投票.

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

正式定义:常规语言的抽取引理

让L成为常规语言.然后存在一个整数p仅取决于≥1 大号使得每个字符串 瓦特在大号长度至少的p(p被称为"泵送长度")可被写为瓦特 = XYZ(即,瓦特可分为三个子字符串),满足以下条件:

1. | y | ≥1
2. | xy | ≤ p
3. 对于所有 我 ≥0,XY ^我 ž ∈ 大号

假设,如果你选择字符串W = a ⁿ b ^m where (n + m) ? p和n > m + 1.选择W是有效的,但是这个选择你无法证明该语言不是常规语言.因为与此W你总是有在-至少一个选择的y=a通过重复与泵在语言新的字符串a为所有的值i (对于i = 0和I> 1) .

在我编写解决方案证明之前,语言不规律.请理解以下几点和注意事项:我在上面提到了泵浦引理的粗体every string w和all i正式定义.

• 虽然语言中有一些足够大的W,但你可以在语言中生成新的字符串,但不可能全部使用!有许多可能的选择w ^(在我的证明下文),同时,你找不到任何选择的Ÿ以产生新的语言字符串,所有的i> = 0.因此,因为每个足够大的W都无法在语言中生成新的字符串,因此语言不常规.

阅读:什么抽样引理形式定义说

证明:使用泵浦引理

步骤(1):选择字符串W = a ⁿ b ^m其中(n + m) ? p和n = m + 1.

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

是的,这样W¯¯是因为许多语言a= N > 的数目b= M.W是语言并且足够大> = p.

步骤(2):现在选择a y为所有人 生成新的字符串i >= 0.

而没有选择是可能的y这个时候!为什么？

首先,我们要了解我们不能b在y中使用符号,因为它会从模式中生成新的字符串,或者在结果字符串中的总数b将超过a符号的总数.

其次,我们不能选择y = some a 's,因为i=0你会得到一个新的字符串,其中as的数量将少于b语言中不可能的数字s.(记住aW中的数字只是一个然后b因此,在结果字符串N(a)= N(b)中删除任何不可接受的均值,因为n> m)

因此,在我们能找到一些W而足够大,但使用的是我们不能产生新的语言字符串,用抽正规语言于是便语言{A的引理性质矛盾^ň b ^米 | n> m}确实不是常规语言.