math - 非上下文无关语言 L 在迭代下是否可能是上下文无关的？

Question

语言 L 不是上下文无关语言。

但是 L* 可以是上下文无关的语言吗？

Answer 1

Yes, this is possible. As an example, consider the alphabet Σ = {1} and let L be the language { 1^p | p is a prime number }. You can prove that this language is not context-free by using the pumping lemma.

However, the language L* is the set of all strings except for 1. The reason for this is that

• ε ∈ L*, because ε ∈ N* for any language N.
• 1² ∈ L* because 2 is prime.
• 1³ ∈ L* because 3 is prime.
• 1ⁿ ∈ L* for any n ≥ 2, because you can start with either 1² or 1³ and concatenate an appropriate number of copies of 1² to it.

This language is indeed context-free, and you can prove that by writing a grammar for it.

Hope this helps!