The language $\mathcal{L}=\{a^n b^n c^n\;|\;n={1,2,3,4}\}$ is not context free from my point of view. Because no. of a's pushed in to stack is totally compensated by no of b's. popped. Please help me.
Also, please tell how to deduce its complement?
[Math] Is this language and its complement is Context free Language
context-free-grammar
Best Answer
$\mathcal L$ is finite, so of course it is regular. Its complement, $\overline{\mathcal{L}}$, is also regular. To see this, note that every word of $\mathcal L$ has length at most $12$. Let $$\mathcal L_0=\big\{w\in\{a,b,c\}^*\setminus\mathcal L:|w|\le 12\big\}\;,$$ and let $$\mathcal L_1=\big\{w\in\{a,b,c\}^*:|w|>12\big\}\;;$$ clearly $\overline{\mathcal{L}}=\mathcal L_0\cup\mathcal L_1$. $\mathcal L_0$ is finite and therefore regular, and it’s easy to see that $\mathcal L_1$ is regular as well: it’s trivial to design a regular grammar that generates $\mathcal L_1$ or a DFA that recognizes it. The union of two regular languages is regular, so $\overline{\mathcal{L}}$ is regular.