0
$\begingroup$

I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not context-free, I am only a beginner at CFG however I thought a language is Context-free if you are able to create a CFG for it, and this is the CFG i created for this language:

S --> aSX | 𝜀 
X --> bXY | 𝜀
Y --> cY | 𝜀

Or am I not understand CFG and what I wrote doesn't make sense?

$\endgroup$
1
$\begingroup$

The grammar you wrote can generate the word "aaa", which is not supposed to be generated, if the grammar generates exactly $L$.

ergo, the grammar is incorrect for $L$. (which is great, since $L$ is not CFL, and no grammar can generate it!)

$\endgroup$
  • $\begingroup$ Oh yeah i forgot about the epsilon, so even if the input aaabbbccc could theoretically be generated nothing stops you from supplying aaa, either, thanks for that $\endgroup$ – john3901 Dec 6 '15 at 14:25

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.