[PDF] CS310 : Automata Theory 2019 Lecture 11: Applications of pumping

View - Download CS310 : Automata Theory 2019 Lecture 11: Applications of pumping

Previous PDF

Next PDF

CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 1CS310 : Automata Theory 2019

Lecture 11: Applications of pumping lemma

Instructor: Ashutosh Gupta

IITB, India

Compile date: 2019-01-28

CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 2Contrapositive of pumping lemma

RecallTheorem 11.1

LetLbe a language.Lis not regular if,fo reach n,there is a w ordw2L such thatjwj nandfo reach b reakupof winto three wordsw=xyzsuch that

1.y6=and

2.jxyj n,

then there is a k0such thatxykz62L. CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 3How to use the pumping lemma?

In the theorem, there are two

exists quantiers, namely wandk.Proving non regularity boils down to the following two quantier instantiations. I

Choose a wordwfor eachn

I Findkfore achb reakupof the wThe instantiations are the creative steps! CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 4Proving a language non regular

Consider languageLI

For eachn, wep roposea w ordwinLlonger thannI

We dene parameterized wordxand non-empty wordysuch that I xyz=wfor somezand

Iparameter space coversall xandysuch thatjxyj n.I

For each splitxandy, we choose aksuch thatxykz62L.We have proven thatLis not regular CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 5Example 1: using pumping lemma

Example 11.1

Consider againLeq=f0n1njn0g.I

For eachnwe need a word. Let it bew= 0n1n.I

The rstncharacters ofware 0n. The breaksxandyare to be from within 0 n.I

Letx= 0iandy= 0j, wherei+jnandj6= 0.

w= 0i|{z} x0 j|{z} y0 nji1n|{z} zI Now we choosek= 0 for eachiandj. The corresponding word is 0 i(0j)00nji1n= 0nj1n:IClearly, 0nj1n62Leq. Therefore,Leqis not regular.iandjare encoding all possible breaks of 0 n. CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 6Example 2: using pumping lemma

Example 11.2

Consider againL=fwjwhas equal number of0and1g.I

For eachnwe need a word. Let it bew= 0n1n.I

The rstncharacters ofware 0n. The breaksxandyare to be from within 0 n.I

Letx= 0iandy= 0j, wherei+jnandj6= 0.

w= 0i|{z} x0 j|{z} y0 nji1n|{z} zI Now we choosek= 0 for eachiandj. The corresponding word is 0 i(0j)00nji1n= 0nj1n:IClearly, 0nj1n62L. Therefore,Lis not regular.iandjare encoding all possible breaks of 0 n. CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 7Example 3: using pumping lemma

Let wordwRbe reverse of wordw.Example 11.3

ConsiderLrev=fwwRjw2 f0;1gg.I

For eachn, letw= 0n110nI

The rstncharacters ofware 0nI

Letx= 0iandy= 0j, wherei+jnandj6= 0.

w= 0i|{z} x0 j|{z} y0 nji110n|{z} zI

Letk= 2 for eachiandj.

0 i(0j)20nji110n= 0n+j110n62Lrev CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 8Example 4: using pumping lemma

Example 11.4

ConsiderLprime=f1pjpis a prime number.g.I

For eachn, letw= 1psuch thatp>n+ 2I

The rstncharacters ofware 1n.I

Letx= 1iandy= 1j, wherei+jnandj6= 0.

w= 1i|{z} x1 j|{z} y1 pji|{z} zI

So,jxykzj= (pj) +kj.I

Letk=pj. Therefore,jxykzj= (pj)(1 +j).I

Since both (pk)>1(why?)and 1 +j>1(why?),xykz62Lprime.Chooseksuch that the term becomes composite? CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 9Example 5: using pumping lemma

Example 11.5

ConsiderL=f1p2jp0g.I

For eachn, letw= 1n2I

The rstncharacters ofware 1n.I

Letx= 1iandy= 1j, wherei+jnandj6= 0.

w= 1i|{z} x1 j|{z} y1 n2ji|{z} zI

So,jxykzj= (n2j) +kj.I

Letk= 2. Therefore,jxykzj=n2+j.I

Since 0Feels like all non-regular languages needed to rememb erinnite memo ry .Example 11.6 Inf0n1njn0gwe need to rememberthe numb erof seen 0s and count the

1s to match.Finite number of statescannot c ountunb oundedlyincreasing numb er.

CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 11More generalized pumping lemma

We have been looking for evidence of

bad pumping in the p rexesof the words.We can look for such evidence for any subword of length greater thann.Theorem 11.2

LetLbe a language.Lis not regular if,

I for eachn,I there are wordsu, andwsuch thatuw2Landjwj nI for each breakup ofwinto three wordsxyz=wsuch thaty6=and jxyj nthenI there is ak0such thatuxykz62L.In our earlier version of pumping lemma,u=. CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 12Converse does not hold! Pumping lemma holds for the following language but is not regular.

L=fcanbnjn1g|{z}

L

1[fcnwjn6= 1 andw2 fa;bgg|{z}

L

2Application of pumping lemma:

I n= 1I

Two casesI

Casetake wordcajbj2L1I

Letx=,y=c, andz=ajbj.I

Fork6= 1,ckajbj2L2, and fork= 1,ckajbj2L1I

Casetake wordcjw2L2forj6= 1

I ......Exercise 11.1

Complete the above application of pumping lemma

CS310 : Automata Theory 2019 Instructor: Ashutosh Gupta IITB, India 13End of Lecture 11quotesdbs_dbs17.pdfusesText_23

[PDF] application of z transform in electronics and communication engineering

[PDF] application of z transform in image processing

[PDF] application of z transform in signals and systems

[PDF] application of z transform pdf

[PDF] application of z transform to solve difference equation

[PDF] application of z transform with justification

[PDF] application pour apprendre l'anglais gratuit sur pc

[PDF] application security risk assessment checklist

[PDF] applications of composite materials

[PDF] applications of dft

[PDF] applications of exponential and logarithmic functions pdf

[PDF] applications of therapeutic drug monitoring

[PDF] applied environmental microbiology nptel

[PDF] applied environmental microbiology nptel pdf

[PDF] applied information and communication technology a level