patternMinor
Why are palindrome and not-palindrome both context-free?
Viewed 0 times
whyfreearebothpalindromecontextandnot
Problem
Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two NCFLs that makes complement work?
Solution
You make the mistake of assuming that
$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \forall\, x \in X. \lnot P(x)$
while in truth
$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \exists\, x \in X. \lnot P(x)$.
In your concrete case, "CFL is not closed against complement" means there are counterexample. You'll recall that REG ⊆ CFL and REG is closed against complement, so there are clearly plenty of complement-pairs in CFL.
As for the concrete two languages, the palindromes are generated by the most archetypical context-free grammar,
$\qquad S \to aSa \mid bSb \mid \dots \mid a \mid b \mid \dots \varepsilon$.
The complement is a nice exercise and can be found elsewhere on the site.
$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \forall\, x \in X. \lnot P(x)$
while in truth
$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \exists\, x \in X. \lnot P(x)$.
In your concrete case, "CFL is not closed against complement" means there are counterexample. You'll recall that REG ⊆ CFL and REG is closed against complement, so there are clearly plenty of complement-pairs in CFL.
As for the concrete two languages, the palindromes are generated by the most archetypical context-free grammar,
$\qquad S \to aSa \mid bSb \mid \dots \mid a \mid b \mid \dots \varepsilon$.
The complement is a nice exercise and can be found elsewhere on the site.
Context
StackExchange Computer Science Q#55294, answer score: 6
Revisions (0)
No revisions yet.