Consider the following grammar $G$: $$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$ Decide if complement of $L(G)$ is also a context-free language.

My approach was to find a word not in the language, such that for any partition that follows the pumping lemma restrictions there exists some pumping that puts the word in the language, but I failed to find such example.

Perhaps the complement is CFL after all. I noticed that the word in $L(G)$ has a characteristic that there exists some substring in the form: $aB^k\#B^kb$. If I managed to find a grammar that generates all words that don't have such substring, that should solve the problem.

I also wanted to ask if there is some intuition to solve these kind of problems, or should I just guess and try to prove it?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.