prev

next

out of 64

View

83Download

2

Embed Size (px)

- 1. THE PUMPING LEMMA
- 2. THE PUMPING LEMMA x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x L
- 3. THE PUMPING LEMMA n x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x L
- 4. THE PUMPING LEMMA n x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x L
- 5. THE PUMPING LEMMA n x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x L
- 6. THE PUMPING LEMMA n x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x u v w L
- 7. THE PUMPING LEMMA n x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x u w u v w L
- 8. THE PUMPING LEMMA n x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x u v wv u w u v w L
- 9. THE PUMPING LEMMA n x Theorem. For any regular language L there exists an integer n, such that for all x L with |x| n, there exist u, v, w , such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) for all i 0: uvi w L. x u v wv u w u v w u v wv v L
- 10. PROOF OF P.L. (SKETCH)
- 11. PROOF OF P.L. (SKETCH) Let M be a DFA for L. Take n be the number of states of M plus 1.
- 12. PROOF OF P.L. (SKETCH) Let M be a DFA for L. Take n be the number of states of M plus 1. Take any x L with |x| n. Consider the path (from start state to an accepting state) in M that corresponds to x. The length of this path is |x| n.
- 13. PROOF OF P.L. (SKETCH) Let M be a DFA for L. Take n be the number of states of M plus 1. Since M has at most n 1 states, some state must be visited twice or more in the rst n steps of the path. Take any x L with |x| n. Consider the path (from start state to an accepting state) in M that corresponds to x. The length of this path is |x| n.
- 14. PROOF OF P.L. (SKETCH) Let M be a DFA for L. Take n be the number of states of M plus 1. Since M has at most n 1 states, some state must be visited twice or more in the rst n steps of the path. Take any x L with |x| n. Consider the path (from start state to an accepting state) in M that corresponds to x. The length of this path is |x| n. u v w
- 15. PROOF OF P.L. (SKETCH) Let M be a DFA for L. Take n be the number of states of M plus 1. Since M has at most n 1 states, some state must be visited twice or more in the rst n steps of the path. Take any x L with |x| n. Consider the path (from start state to an accepting state) in M that corresponds to x. The length of this path is |x| n. u v w x = uvw L uw L uvvw L uvvvw L . . .
- 16. L regular = L satises P.L. L non-regular = ? L non-regular = L doesnt satisfy P.L. Negation: n N x L with |x| n u, v, w all of these hold: (1) x = uvw (2) |uv| n (3) |v| 1 (4) i 0: uvi w L. USING PUMPING LEMMA TO PROVE NON-REGULARITY
- 17. L regular = L satises P.L. L non-regular = ? L non-regular = L doesnt satisfy P.L. Negation: n N x L with |x| n u, v, w all of these hold: (1) x = uvw (2) |uv| n (3) |v| 1 (4) i 0: uvi w L. USING PUMPING LEMMA TO PROVE NON-REGULARITY
- 18. L regular = L satises P.L. L non-regular = ? L non-regular = L doesnt satisfy P.L. Negation: n N x L with |x| n u, v, w all of these hold: (1) x = uvw (2) |uv| n (3) |v| 1 (4) i 0: uvi w L. n N x L with |x| n u, v, w not all of these hold: (1) x = uvw (2) |uv| n (3) |v| 1 (4) i 0: uvi w L. USING PUMPING LEMMA TO PROVE NON-REGULARITY
- 19. L regular = L satises P.L. L non-regular = ? L non-regular = L doesnt satisfy P.L. Negation: n N x L with |x| n u, v, w all of these hold: (1) x = uvw (2) |uv| n (3) |v| 1 (4) i 0: uvi w L. n N x L with |x| n u, v, w not all of these hold: (1) x = uvw (2) |uv| n (3) |v| 1 (4) i 0: uvi w L. Equivalently: (1) (2) (3) not(4) where not(4) is: i : uvi w L USING PUMPING LEMMA TO PROVE NON-REGULARITY
- 20. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular.
- 21. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity).
- 22. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . .
- 23. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n
- 24. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n x L and |x| n, so by P.L. u, v, w such that (1)(4) hold.
- 25. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n x L and |x| n, so by P.L. u, v, w such that (1)(4) hold. We show that u, v, w (1)(4) dont all hold.
- 26. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n x L and |x| n, so by P.L. u, v, w such that (1)(4) hold. We show that u, v, w (1)(4) dont all hold. If (1), (2), (3) hold then x = 0n 1n = uvw with |uv| n and |v| 1.
- 27. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n x L and |x| n, so by P.L. u, v, w such that (1)(4) hold. We show that u, v, w (1)(4) dont all hold. If (1), (2), (3) hold then x = 0n 1n = uvw with |uv| n and |v| 1. So, u = 0s , v = 0t , w = 0p 1n with
- 28. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n x L and |x| n, so by P.L. u, v, w such that (1)(4) hold. We show that u, v, w (1)(4) dont all hold. If (1), (2), (3) hold then x = 0n 1n = uvw with |uv| n and |v| 1. So, u = 0s , v = 0t , w = 0p 1n with s + t n, t 1, p 0, s + t + p = n.
- 29. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n x L and |x| n, so by P.L. u, v, w such that (1)(4) hold. We show that u, v, w (1)(4) dont all hold. If (1), (2), (3) hold then x = 0n 1n = uvw with |uv| n and |v| 1. But then (4) fails for i = 0: So, u = 0s , v = 0t , w = 0p 1n with s + t n, t 1, p 0, s + t + p = n.
- 30. EXAMPLE 1 Prove that L = {0i 1i : i 0} is NOT regular. Proof. Show that P.L. doesnt hold (note: showing P.L. holds doesnt mean regularity). If L is regular, then by P.L. n such that . . . Now let x = 0n 1n x L and |x| n, so by P.L. u, v, w such that (1)(4) hold. We show that u, v, w (1)(4) dont all hold. If (1), (2), (3) hold then x = 0n 1n = uvw with |uv| n and |v| 1. But then (4) fails for i = 0: uv0 w = uw = 0s 0p 1n = 0s+p 1n L, since s + p = n So, u = 0s , v = 0t , w = 0p 1n with s + t n, t 1, p 0, s + t + p = n.
- 31. IN PICTURE u, v, w such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) i N : uvi w L.
- 32. IN PICTURE u, v, w such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) i N : uvi w L. u00000 v0 . . . w01111 . . . 1 L
- 33. IN PICTURE u, v, w such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) i N : uvi w L. u00000 v0 . . . w01111 . . . 1 L non-empty
- 34. IN PICTURE u, v, w such that (1) x = uvw (2) |uv| n (3) |v| 1 (4) i N : uvi w L. u00000 v0 . . . w01111 . . . 1 L non-empty If (1), (2), (3) hold then (4) fails: it is not the case that for all i, uvi w is in L. In particular, let i = 0. uw L.
- 35. EXAMPLE 2 Prove that L = {0i : i is a prime} is NOT regular.
- 36. EXAMPLE 2 Prove that L = {0i : i is a prime} is NOT regular. Proof. We show that P.L. doesnt hold.
- 37. EXAMPLE 2 If L is regular, then by P.L. n such that . . . Prove that L = {0i : i is a prime} is NOT regular. Proof. We show that P.L. doesnt hold.
- 38. EXAMPLE 2 If L is regular, then by P.L. n such that . . . Prove that L = {0i : i is a prime} is NOT regular. Now let x = 0m where m n + 2 is prime. Proof. We show that P.L. doesnt hold.
- 39. EXAMPLE 2 If L is regular, then by P.L. n such that . . . Prove that L = {0i : i is a prime} is NOT regular. Now let x = 0m where m n + 2 is prime. x L and |x| n, so by P.L. u, v, w such that (1)(4) hold. Proof. We show that P.L. doesnt hold.