際際滷

際際滷Share a Scribd company logo

Pumping lemma numerical

D
Dr. ABHISHEK K PANDEY

The document applies the pumping lemma to a language L to show that L is not regular. It chooses a string w in L of length at least m, where m is the pumping length. It then shows that w can be pumped to generate strings both in and not in L, resulting in a contradiction. This contradiction means the assumption that L is regular is false, so L must be non-regular.

1 of 8
1
2 mmm cbaw 2 We pick Let be the integer in the Pumping Lemma Pick a string such that: w Lw mw ||length m }0,:{ 鰹 lncbaL lnln and
3 Write zyxcba mmm 2 it must be that length From the Pumping Lemma cccbcabaaaaaxyz .................. x y z m m m2 1||,|| 鰹 ymyx 1, 鰹 kay kThus:
4 From the Pumping Lemma: Lzyx i ...,2,1,0i Thus: mmm cbazyx 2 Lxzzyx =0 1, 鰹 kay k
5 From the Pumping Lemma: Lcccbcabaaaxz ............... x z km m m2 mmm cbazyx 2 1, 鰹 kay k Lxz Thus: Lcba mmkm 2
6 Lcba mmkm 2 Lcba mmkm 2 BUT: CONTRADICTION!!! }0,:{ 鰹 lncbaL lnln 1k
7 Our assumption that is a regular language is not true L Conclusion: L is not a regular language Therefore:
8 Regular languages Non-regular languages }0:{ ! 鰹 naL n

More Related Content

Pumping lemma numerical