1

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

guglielmo
  • 31
  • Point 2 your friend used is wrong. There are plenty of languages such that neither $C$ nor its complement is context-free. Any non-decidable language is an example. – Tzimmo Dec 17 '23 at 15:05
  • I know that, another way to solve the exercise? – guglielmo Dec 17 '23 at 15:19
  • Sorry, it wasn't clear whether you were asking if your friend was correct or for a better solution. A word is not in $C$ if it doesn't have the form $a#b#c#$, if $a \neq b^R$, or $b \neq c^R$ does this help? – Tzimmo Dec 17 '23 at 16:21

0 Answers0