NANJING UNIVERSITY The Pumping Lemma for CFL's Statement Applications .1
Statement Applications The Pumping Lemma for CFL’s 1
效绵鼎 Intuition Recall the pumping lemma for regular languages. It told us that if there was a string long enough to cause a cycle in the DFA for the language,then we could "pump"the cycle and discover an infinite sequence of strings that had to be in the language. 2
Intuition ◼ Recall the pumping lemma for regular languages. ◼ It told us that if there was a string long enough to cause a cycle in the DFA for the language, then we could “ pump” the cycle and discover an infinite sequence of strings that had to be in the language. 2
效绵鼎 Intuition-(2) For CFL's the situation is a little more complicated. ■ We can always find two pieces of any sufficiently long string to“pump”in tandem. o That is:if we repeat each of the two pieces the same number of times,we get another string in the language. 3
Intuition – (2) ◼ For CFL’s the situation is a little more complicated. ◼ We can always find two pieces of any sufficiently long string to “ pump” in tandem. That is: if we repeat each of the two pieces the same number of times, we get another string in the language. 3
效绵鼎 Statement of the CFL Pumping Lemma For every context-free language L There is an integer n,such that For every string z in L of length >n There exists z uvwxy such that: 1. wwx≤n. 2 vx>0. 3.For all i>0,uv'wx'y is in L 4
Statement of the CFL Pumping Lemma For every context-free language L There is an integer n, such that For every string z in L of length > n There exists z = uvwxy such that: 1. |vwx| 0. 3. For all i > 0, uviwxiy is in L. 4
效绵鼎 Proof of the Pumping Lemma Start with a CNF grammar for L-{e). Let the grammar have m variables. Pick n=2m. Let z,of length >n,be in L. We claim(“Lemma 1”)that a parse tree with yield z must have a path of length m+2 or more. .5
Proof of the Pumping Lemma ◼ Start with a CNF grammar for L – {ε}. ◼ Let the grammar have m variables. ◼ Pick n = 2m. ◼ Let z, of length > n, be in L. ◼ We claim (“Lemma 1 ”) that a parse tree with yield z must have a path of length m+2 or more. 5
效绵鼎 Proof of Lemma 1 If all paths in the parse tree of a CNF grammar are of length m+1,then the longest yield has length 2m-1,as in: m variables one terminal 2m-1 terminals 6
Proof of Lemma 1 ◼ If all paths in the parse tree of a CNF grammar are of length < m+1, then the longest yield has length 2 m-1 , as in: 6 m variables one terminal 2 m-1 terminals
效绵县 Back to the Proof of the Pumping Lemma Now we know that the parse tree for z has a path with at least m+1 variables. Consider some longest path. There are only m different variables,so among the lowest m+1 we can find two nodes with the same label,say A. The parse tree thus looks like: 7
Back to the Proof of the Pumping Lemma ◼ Now we know that the parse tree for z has a path with at least m+1 variables. ◼ Consider some longest path. ◼ There are only m different variables, so among the lowest m+1 we can find two nodes with the same label, say A. ◼ The parse tree thus looks like: 7
效绵易 Parse Tree in the Pumping-Lemma Preol ≤2m=n because a longest path chosen Can't both and only the bottom be c. m+1 variables used. A A V W X y 8
Parse Tree in the Pumping-Lemma Proof 8 < 2 m = n because a longest path chosen and only the bottom m+1 variables used. A A u v w x y Can’t both be ε
效绵鼎 Pump Zero Times A W U W X y y 9
Pump Zero Times 9 u y A v x A w u y A w
效绵鼎 Pump Twice W X y y W X .10
Pump Twice 10 u y A v x A w u y A w A v x A v x