2-19-08 class notes PDF

Preview

Summary

...

Description

CSE355 Class Notes - 2/19/2008 Pumping Lemma: If L is a regular language then there exists a number m such that for all strings w of length  m, w can be written as xyz such that: (i) xyix  L, for i  0 (ii) |y|  1 (iii) |xy|  m Example: L1 = {anbn | n  1}, show that L1 is not regular. Proof: Suppose L1 is regular. Then it must satisfy the pumping lemma. Let m be the number in the pumping lemma. Now consider w = ambm Let us break w to xyz such that |xy|  m. There are two possible cases:

(i) (ii)

aa………………a bb………………b |---x---|---y---|-----------------z----------| |----x----|----y-----|------------z----------|

Case (i): xy2z has more a’s than b’s, so xy2z is not in L1 Case (ii): xy 2z has more a’s than b’s, so xy2z is not in L1 Thus, there is no way to break w to xyz to satisfy the conditions of the pumping lemma. L1 does not satisfy the pumping lemma. Hence, L1 cannot be a regular language. Example: L2 = {ww | w  {0,1}*}, show that L2 is not regular. Proof: Suppose L2 is regular. Then it must satisfy the pumping lemma. Let m be the number in the pumping lemma. Now consider w = 0m10 m 1 Let us break w to xyz such that |xy|  m. There are two possible cases:

(i) (ii)

00………………01 00………………01 |---x---|---y---|-----------------z-------------| |----x----|----y-----|------------z-------------|

Case (i): xy2z has more 0’s in the first string than the second string, so xy2 z is not in L2 Case (ii): xy 2z has more 0’s in the first string than the second string, so xy2z is not in L2 Thus, there is no way to break w to xyz to satisfy the conditions of the pumping lemma. L2 does not satisfy the pumping lemma. Hence, L2 cannot be a regular language....