I have this language:
$L = \{a^nb^nc^kd^k∣n > k\}$
I get why $L$ isn't context free, but why $\bar{L}$ context free?
1 Answer
$\begingroup$
$\endgroup$
2
A pushdown automaton trying to decide $\overline{L}$ can just non-deterministically guess the ``reason'' while the input word doesn't belong to $L$. The potential reasons will be:
- The word isnt of the form $a^nb^mc^jd^i$.
- The word has an unequal number of $a$'s and $b$'s.
- The word has no more $b$'s than $c$'s.
- The word has an unequal number of $c$'s and $d$'s.
Each individual condition can be checked by a pushdown automaton, so we're good.
-
$\begingroup$ What about, for instance, The word has no more a's than c's, or the word has no more a's than d's etc. $\endgroup$Yahli Gitzi– Yahli Gitzi2025-02-14 08:36:34 +00:00Commented Feb 14 at 8:36
-
$\begingroup$ @YahliGitzi Those are covered by the cases I listed. Eg "no more a's than c's" means at least one of 2 and 3 have to trigger. $\endgroup$Arno– Arno2025-02-14 10:59:35 +00:00Commented Feb 14 at 10:59