1
$\begingroup$

I understand intuitively why the pumping lemma for regular languages must hold. That is to recognize a infinite string with a finite amount of states you must repeat states and you can "pump" those repeated states as many times as you wish.

However for the context free language version I can't seem to come up with the same intuitive understanding for why the lemma holds. My textbook mentions abusing the fact every CFG can be put into Chomsky normal form and then using some properties of binary trees to show productions can be pumped but Im having a hard time following why this would lead to repeated states, let alone two repeated states.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

A context-free grammar has a finite number of nonterminals. This means the number of different derivation trees you can generate such that each nonterminal on each path of each tree is different is also finite: if you have $n$ nonterminals, then each path longer than $n$ will contain at least one nonterminal twice. That means all other derivations have a repeating nonterminal $A$ on some path. We can then pump by repeating the path segment from $A$ to $A$ arbitrarily often. This remains true after we make the grammar proper by removing all unproductive and unreachable nonterminals and cyclic rules.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So to have a path longer than the number of productions you would need to repeat some production. That makes sense. How would this lead to two and only two "pumpable" paths though? $\endgroup$
    – Mitch
    Nov 5, 2018 at 16:38
  • $\begingroup$ It's not only two. All paths longer than $n$ in the proper grammar have at least one repeating nonterminal, and hence, are pumpable (and have already been pumped at least once). All strings generated by such paths are the result of pumping one of the (finite set of) unpumped strings at least once, and that pumping can be repeated arbitrarily often. $\endgroup$
    – reinierpost
    Nov 5, 2018 at 16:58
1
$\begingroup$

Im not sure what the rule is in linking to off site resources but I found this video particularity helpful in getting an intuitive understanding for the pumping lemma for CFGs

The idea is that a sufficiently long string will have some repeated path along it from root to leaf. This path can be repeated as many times as we wish. The left side and the right side of the tree will be "pumped" and the the characters in the center of the subtree will remain. This is where we get x^n y z^n substring from the pumping lemma. I highly recommend watching the video however, it is explained much better and the visualization helps.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Linking to off-site resources is fine, as is answering your own question. But could you please give a short summary of what the intuition is? That would be useful both in case the video ever gets taken down and also for people who might not be able to watch videos where they are. $\endgroup$
    – David Richerby
    Nov 17, 2018 at 19:42
  • $\begingroup$ @DavidRicherby I did my best to summarize it $\endgroup$
    – Mitch
    Nov 17, 2018 at 20:20

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.