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?
