Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?

Question

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\}$.)

Answer 1

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 \} $$