This question appeared on my Theory of Computer Science final:

True | False: $A^*$ is context-free $\implies$ $A$ is context-free.

My professor says the answer is false, and I believe him, but am having trouble constructing a counterexample or even just convincing myself why. It seems to me that if a grammar can describe repeated concatenation, there must be some nonterminal that is concatenated.

Does anyone have a counterexample?


Let $L$ be any non-context-free language, then we can construct the language $A = \Sigma\cup L$ - i.e. $A$ is either an element of $\Sigma$ or a string from $L$ (these can happily overlap too). This is clearly not context free either (if it were, then we would have a PDA for it, and we can easily modify this PDA to recognise $L$).

If we now take $A^{\ast}$ however, we get $\Sigma^{\ast}$, which is most certainly context free.

  • $\begingroup$ Awesome, this is a really clear construction. $\endgroup$ – Eli Rose May 16 '14 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.