[PDF] [PDF] Applications of pumping lemma - Cse iitb

[PDF] More Applications of The Pumping Lemma

Context Free Languages – Context Free Grammars – Derivations: leftmost, rightmost and derivation trees – Parsing and ambiguity – Simplifications and 

[PDF] The Pumping Lemma For Regular Languages

How do we prove that a Language is NOT Regular? Page 3 Examples of Nonregular Languages ○ B = {0n 1

[PDF] Applications of pumping lemma - Cse iitb

28 jan 2019 · Theorem 11 1 Let L be a language L is not regular if, for each n, there is a word w ∈ L such that w ≥ n and for each breakup of w into three 

[PDF] The Application of Pumping Lemma on Context Free Grammars

and the terminal strings constitute the language generated by the PCGS Here we apply pumping lemma on certain languages to show that, they are not context  

[PDF] proving languages not regular using Pumping Lemma

Here is the Pumping Lemma If L is a regular language, then there is an integer n > 0 with the property that: (*) for any string x ∈ L where x ≥ n, there are strings u, v, w such that (i) x = uvw, (ii) v = ǫ, (iii) uv ≤ n, (iv) uvkw ∈ L for all k ∈ N

[PDF] Regular Languages and Pumping Lemma 1 Regular Operations

11 fév 2020 · As a sanity check, a single string can be written as the concatenation of its characters For example {abc} = {a}◦{b}◦{c}, and a set of strings is 

[PDF] Notes on Pumping Lemma

5 mar 2018 · We can use a variety of tools in order to show that a certain language is regular For example, we can give a finite automaton that recognises 

[PDF] Non-regular languages and the pumping lemma - MIT

Existence of non-regular languages • Theorem: There is a language over Σ = { 0, 1 } that is not regular • (Works for other alphabets too ) • Proof: – Recall 

[PDF] Pumping Lemma - Ashutosh Trivedi

Pumping Lemma: Proof Theorem (Pumping Lemma for Regular Languages) If L is a regular language, then there exists a constant p such that for every string

[PDF] CS5371 Theory of Computation

•Prove the Pumping Lemma, and use it to show that there are non-regular languages •Introduce Regular Expression –which is one way to describe a language

[PDF] application of z transform in digital filters

[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

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