pumping-lemma - CFL 的抽引引理 a^nb^mc^o 为 n 假设： L={a n b m c o | n < m < o, n natural} 使用抽水引理我选择了： z = uvwxy = a n b n+1 c n+2 |uv|<=n 和 |v|>0 => uv <

Question

假设： L={a ⁿ b ^m c ^o | n < m < o, n natural}
使用抽水引理我选择了： z = uvwxy = a ⁿ b ⁿ⁺¹ c ⁿ⁺²
|uv|<=n 和 |v|>0
=> uv ² wx ² y
If vwx 属于 a 和/或 b 没关系，我们将拥有比 c 更多的 a 和/或 b - 但如果 vwx 仅包含 c，它将是 L 的元素。
据我所知，所有新词都必须不是元素L 以表明它不是 CFL。我该怎么做？

Answer 1

如果我们有 a 和 b 的混合使用 uv ² wx ² y
如果我们有 b 和 c 的混合使用 uv ⁰ wx ⁰ y

现在所有通过抽取 z 创建的单词都不是 L 的元素。