上下文无关语言问题(Pumping Lemma) [英] Context Free Language Question (Pumping Lemma)

问题描述

我知道这与编程没有直接关系，但我想知道是否有人知道如何将泵引理应用于以下证明:

I know this isn't directly related to programming, but I was wondering if anyone know how to apply the pumping lemma to the following proof:

证明 L={(a^n)(b^n)(c^m) : n!=m} 不是上下文无关语言

Show that L={(a^n)(b^n)(c^m) : n!=m} is not a context free language

我对应用抽水引理非常有信心，但这真的让我很恼火.你怎么看?

I'm pretty confident with applying pumping lemmas, but this one is really irking me. What do you think?

推荐答案

我完全把你引向了错误的轨道.这就是当我自己还没有完全解决问题时尝试提供帮助时会发生的情况.

I was totally leading you down the wrong track. That's what happens when I try to help out when I haven't completely solved the problem myself.

假设 L 是上下文无关的.根据奥格登引理，存在具有以下性质的整数 p:

Suppose L is context free. By Ogden's lemma, there exists an integer p that has the following properties:

给定L中至少有p个符号长的字符串w，其中至少p个符号被标记"，w可以表示为uvxyz，满足:

Given a string w in L at least p symbols long, where at least p of those symbols are "marked", w can be represented as uvxyz, which satisfy:

1. x 至少有一个标记符号，
2. 要么 u 和 v 都有标记符号，要么 y 和 z 都有标记符号，
3. vxy 最多有 p 个标记符号，并且
4. u vⁱ x yⁱ z 在 L 中，因为 i >= 0

1. x has at least one marked symbol,
2. either u and v both have marked symbols or y and z both have marked symbols,
3. vxy has at most p marked symbols, and
4. u vⁱ x yⁱ z is in L for i >= 0

这是奥格登引理.现在，让 q 是一个整数，可以被每个不大于 p 的正整数整除.设 w = a^p+q b^p+q c^p.标记每个 c.通过#2，u 或v 必须至少包含一个c.如果 u 或 v 包含任何其他符号，则#4 失败，因此 u 和 v 必须仅包含 c.但是当 i = q/|uv| 时，#4 失败了.我们知道 q 可以被 |uv| 整除因为 p > |uv|> 0，并且 q 可以被所有小于 p 的正整数整除.

That's Ogden's lemma. Now, let q be an integer divisible by every positive integer no greater than p. Let w = a^p+q b^p+q c^p. Mark every c. By #2, u or v must contain at least one c. If either u or v contains any other symbol, then #4 fails, so u and v must contain only c. But then #4 fails when i = q/|uv|. We know q is divisible by |uv| because p > |uv| > 0, and q is divisible by all positive integers less than p.

请注意，当您标记所有符号时，奥格登引理会变成泵引理.

Note that Ogden's lemma turns into the pumping lemma when you mark all symbols.

假设 L 是上下文无关的.通过抽引引理，有一个长度 p(不一定与上面的 p 相同)使得 L 中的任何字符串 w 都可以表示为 uvxyz，其中

Suppose L is context free. By the pumping lemma, there is a length p (not necessarily the same p as above) such that any string w in L can be represented as uvxyz, where

1. |vxy|<= p,
2. |维|>= 1，和
3. u vⁱ x yⁱ z 在 L 中，因为 i >= 0.

1. |vxy| <= p,
2. |vy| >= 1, and
3. u vⁱ x yⁱ z is in L for i >= 0.

给定 L 中的字符串 w，要么 m > n 要么 m

Given a string w in L, either m > n or m < n. Suppose p = 2.

假设 m > n.(注意 Λ 表示空字符串.)

Suppose that m > n. (Note that Λ denotes the empty string.)

• 让 u = aⁿ bⁿ c^m-1
• 设 v = c
• 设 x = Λ
• 令y = Λ
• 设 z = Λ

假设 n > m.

• 让 u = a^n-1
• 设 v = a
• 设 x = Λ
• 让y = b
• 设 z = b^n-1 c^m

这表明 L 中的任何字符串都没有提供使用泵引理来假设 L 是上下文无关语言(即使它是上下文敏感的)的反例.

This demonstrates that no string from L provides a counterexample using the pumping lemma to the supposition that L is a context free language (even though it is context sensitive).

这篇关于上下文无关语言问题(Pumping Lemma)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！