1
$\begingroup$

According to this statement:

Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular language and its complement are a pair of complementary context-free languages.

$\{a^n b^n c^n \mid n\ge0\}$ is not deterministic context-free language so is $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$ a deterministic context-free language? If it is, how does it look like?

($\Sigma^*$ means every possible string that can be generated with $\{a,b,c\}$.)

$\endgroup$
2
$\begingroup$

The complement of a deterministic context-free language is also deterministic context-free. Since $\{a^nb^nc^n \mid n \geq 0\}$ is not context-free, its complement cannot be deterministic context-free. However, the complement is context-free, since it can be written as follows: $$ \overline{a^*b^*c^*} \cup \{a^{n+k} b^n c^m, a^n b^{n+k} c^m, a^{n+k} b^m c^n, a^n b^m c^{n+k}, a^m b^{n+k} c^n, a^m b^n c^{n+k} \mid n,m \ge 0, k \ge 1 \} $$

$\endgroup$
3
  • $\begingroup$ You're right and I upvoted your answer but I want the pushdown automata diagram. $\endgroup$ – Vala Khosravi Dec 17 '20 at 13:43
  • $\begingroup$ Well, you won’t get it from me, since you can work it out on your own. $\endgroup$ – Yuval Filmus Dec 17 '20 at 13:43
  • $\begingroup$ Ok, and thanks for the edit. $\endgroup$ – Vala Khosravi Dec 17 '20 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.