Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\to$ Dd | d$\}$ seems to be the desired CFG. By the Pumping lemma for CFG, I understand that it is not context-free but that seems very much contradictory.
Can someone clarify this? I got this doubt while I wondering if CFGs can generate all languages.
Your grammar generates the language $\{a^ib^jc^kd^\ell \mid i,j,k,l \geq 1\}$, which is larger than $\{a^nb^nc^nd^n \mid n \geq 1\}$. For example, your grammar generates $abcdd$, which is not of the form $a^nb^nc^nd^n$.
That said, you can generate $\{a^nb^nc^nd^n \mid n \geq 1\}$ using a context-sensitive grammar. Moreover, unrestricted grammar can generate all recursively enumerable languages.
