Cheap and Secure Web Hosting Provider : See Now

[Solved]: Situations where Kleene star of A is context-free, but A is not

, , No Comments
Problem Detail: 

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?

Asked By : Eli Rose

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24786

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback