南京大学：《形式语言与自动机 Formal Languages and Automata》课程教学资源（PPT课件讲稿）Properties of CFL（The Pumping Lemma for CFL’s）

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