$\sum=\{0, 1, \#\}$ $C=\{x\#x^R\#x\# | x \in \{0, 1\}^*\}$ Show C̄ is CFL

24 Views Asked by At

From my Automata class

$\sum=\{0, 1, \#\}$ $C=\{x\#x^R\#x\# | x \in \{0, 1\}^*\}$ Show C̄ is CFL

I want to use pumping lemma for CFL but I can’t understand which type of language is the complement of C.

Some of my friend proved by:

  1. {… demonstration that C is not CFL via PL}
  2. Thus C is not a context free language.In other words, it can be said that C̄ is a context free language

But I can’t understand why the fact that if C is not CFL implies that C̄ is CFL

I think that’s not a correct way of thinking