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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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!)

Improve this answer
$\endgroup$
1
  • $\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, 2015 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.