[PDF] [PDF] proving languages not regular using Pumping Lemma

[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

CSC B36 Additional Notesproving languagesnotregular using Pumping Lemma c?Nick Cheng

?IntroductionThe Pumping Lemma is used for proving that a language isnotregular. Here is the Pumping Lemma.

IfLis a regular language, then there is an integern >0 with the property that: (*)for any stringx?Lwhere|x| ≥n, there are stringsu,v,wsuch that (i)x=uvw, (ii)v?=?, (iv)uvkw?Lfor allk?N. To prove that a languageLisnotregular, we use proof by contradiction. Here are the steps.

1. Suppose thatLisregular.

2. SinceLis regular, we apply the Pumping Lemma and assert the existence of a numbern >0 that

satisfies the property (*).

3. Give a particular stringxsuch that

(a)x?L, (b)|x| ≥n. This the trickiest part. A wrong choice here will make step 4 impossible.

4. By Pumping Lemma, there are stringsu,v,wsuch that (i)-(iv) hold. Pick a particular numberk?N

and argue thatuvkw??L, thus yielding our desired contradiction. What follows are two example proofs using Pumping Lemma. CSC B36 proving languages not regular using Pumping Lemma Page 1 of 3 ?A (relatively) easy exampleLetL={0k1k:k?N}. We prove thatLis not regular. [step 1]

By way of contradiction, supposeLis regular.

[step 2]

Letnbe as in the Pumping Lemma.

[step 3]

Letx= 0n1n.

Thenx?L[definition ofL]

and|x|= 2n≥n. [step 4]

By Pumping Lemma, there are stringsu,v,wsuch that

(i)x=uvw, (ii)v?=?, (iv)uvkw?Lfor allk?N. Letybe the prefix ofxwith lengthn. I.e.,yis the firstnsymbols ofx.

By our choice ofx,y= 0n.

By (iv),uv2w?L.(#)

Aside:We are pickingk= 2. Indeed, anyk?= 1 will do here.

However,uv2w=uvvw

= 0 n+j1n ??L, [definition ofL; sincej >0,n+j?=n] which contradicts (#).

ThereforeLis not regular.?

CSC B36 proving languages not regular using Pumping Lemma Page 2 of 3 ?A harder exampleLetL={(10)p1q:p,q?N,p≥q}. We prove thatLis not regular. [step 1]

By way of contradiction, supposeLis regular.

[step 2]

Letnbe as in the Pumping Lemma.

[step 3]

Letx= (10)n1n.

Thenx?L[definition ofL]

and|x|= 3n≥n. [step 4]

By Pumping Lemma, there are stringsu,v,wsuch that

(i)x=uvw, (ii)v?=?, (iv)uvkw?Lfor allk?N.

Letybe the prefix ofxwith lengthn.

By our choice ofx,y= (10)n

2ifnis even, andy= (10)n-121 ifnis odd.

By (i) and (iii),uvis a prefix ofy, and

2, or 2. Combining with (ii) - depending on whether|uv|is even or odd, 2, or 2.

There are 3 cases to consider:

(a)vstarts with 0 and ends with 0. (b)vstarts with 1 and ends with 1. (c)vstarts and ends with different symbols.

For case (a),uv0w=uwcontains 110 as a substring.

Thusuv0w??L, [110 is not a substring of any string inL] which contradicts (iv). Similarly for case (b),uv0wcontains 00 as a substring.[details left to reader]

For case (c),v= (10)iorv= (01)i, where 0< i.

So|v|= 2i.

Thusuv0w=uw= (10)n-i1n??L, [definition ofL;n-i < n] which contradicts (iv).

We reach a contradiction in all cases.

ThereforeLis not regular.?

CSC B36 proving languages not regular using Pumping Lemma Page 3 of 3quotesdbs_dbs17.pdfusesText_23