1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.