效绵鼎 Pump Thrice Etc.,Etc. W y y W .11
Pump Thrice 11 u y A v x A w u y A w A v x A v x A v x Etc., Etc
效绵鼎 Using the Pumping Lemma {0l0i|i≥1}is a CFL. o We can match one pair of counts. ■ But L={01010i>1 is not. o We can't match two pairs,or three counts as a group. ■ Proof using the pumping lemma. Suppose L were a CFL. Let n be L's pumping-lemma constant. .12
Using the Pumping Lemma ◼ {0i10i | i > 1} is a CFL. We can match one pair of counts. ◼ But L = {0i10i10i | i > 1} is not. We can’t match two pairs, or three counts as a group. ◼ Proof using the pumping lemma. ◼ Suppose L were a CFL. ◼ Let n be L’s pumping-lemma constant. 12
效绵鼎 Using the Pumping Lemma-(2) Consider z=on10n10n. We can write z=uvwxy,where lvwx≤n,and |vx≥ 1. Case 1:vx has no 0's. 0 Then at least one of them is a 1,and uwy has at most one 1,which no string in L does. .13
Using the Pumping Lemma – (2) ◼ Consider z = 0n10n10n . ◼ We can write z = uvwxy, where |vwx| < n, and |vx| > 1. ◼ Case 1: vx has no 0’s. Then at least one of them is a 1, and uwy has at most one 1, which no string in L does. 13
效绵县 Using the Pumping Lemma-(3) Still considering z=on10n10n. Case 2:vx has at least one 0. vwx is too short (length n)to extend to all three blocks of0's in On1on10n. 0 Thus,uwy has at least one block of n 0's,and at least one block with fewer than n 0's. 0 Thus,uwy is not in L. .14
Using the Pumping Lemma – (3) ◼ Still considering z = 0n10n10n . ◼ Case 2: vx has at least one 0. vwx is too short (length < n) to extend to all three blocks of 0’s in 0n10n10n . Thus, uwy has at least one block of n 0’s, and at least one block with fewer than n 0’s. Thus, uwy is not in L. 14
NANJING UNIVERSITY Properties of Context-Free Languages Decision Properties Closure Properties .15
Decision Properties Closure Properties Properties of Context-Free Languages 15