[PDF] The Pumping Lemma for CFLs and Properties of Context-Free

View - Download The Pumping Lemma for CFLs and Properties of Context-Free

Previous PDF

Next PDF

BBM401 Automata Theory and Formal Languages1

The Pumping Lemma for CFLsand

Properties of Context-Free Languages

The Pumping Lemma for CFLs

BBM401 Automata Theory and Formal Languages2

Intuition:

The pumping lemma of regular languages tell us that If there was a string long enough to cause a cycle in the DFA for the language, then we could (a pieceof thestring)and discover an infinite sequence of strings that had to be in the language. The pumping lemma of context-freelanguages tell us that If there was a string long enough to cause a cycle(samevariableappears morethanoncein thederivation), thenwe can always find two pieces of this sufficiently tandemand discover an infinite sequence of strings that had to be in the language. That is: if we repeat each of the two pieces the same number of times, we get another string in the language.

The Pumping Lemma for CFLs

BBM401 Automata Theory and Formal Languages3

Thefirst step in deriving a pumping lemma for CFLs is to examine the shape and size of parse trees. One of the uses of Chomsky Normal Form (CNF)is to turn parse trees into binary trees. RememberthateveryCFG can be convertedtoan equivalentgrammarin CNF, and A context-free grammar is in Chomsky Normal Form if every rule is of the form

ĺorĺ

THEOREM: The Size of Parse Trees forGrammarsin CNF Suppose we have a parse tree according to a Chomsky-Normal-Form grammar G = (V, T, P, S), and suppose that the yield of the tree is a terminal string w.

If the length of the longest path is n, thenn-l.

The Pumping Lemma for CFLs

The Size of Parse Trees

BBM401 Automata Theory and Formal Languages4

THEOREM: (The pumping lemma for context-free languages) Let L be a CFL, then there exists a constant nsuch that if zis any string in L such that|z|is at least n, then we can write z = uvwxy, subject to the following conditions:

1.|vwx|nThat is, the middle portion is not too long.

2.vxSince vand xare the pieces to be "pumped," this condition says

that at least one of the strings we pump must not be empty.

3.For alliuviwxiy is in L.

That is, the two strings vand xmay be"pumped" any number of times, including 0, and the resulting string will still be a member of L.

The Pumping Lemma for CFLs

BBM401 Automata Theory and Formal Languages5

Thefirststep is to find a ChomskyNormalForm grammar G for languageL. IfL is , {} orit contains, thisdoesnot causeanyproblem in theproof. If L is or{} then the statement of the theorem, whichtalks about a non-emptystring z in Lsurely cannot be violated, sincethere is no such z in L in thiscase. Also, ifL contains, thenit is not alsoa problem, theselectedstringz mustbe non-empty. Now, startingwith a CNF grammar G=(V,T,P,S) such that L(G)=L-{}.

Let the grammar have mvariables.

Pick n = 2m.

Let |z| >n.

ShapeOfParseTreeClaimz must

have a path of length m+2or more.

Proofof the Pumping Lemma for CFLs

BBM401 Automata Theory and Formal Languages6

If the length of the longest path in the parse tree of a CNF grammar is m+1, then the longest yield has length 2m-1, and there are mvariables on the longest path. If the length of the longest path in the parse tree of a CNF grammar is m+2, then the longest yield has length 2m, and there are m+1variables on the longest path.

Proofof the Pumping Lemma for CFLs

Shapeof ParseTreeforCNF Grammars

BBM401 Automata Theory and Formal Languages7

2m-1terminals

variables longest path length is m+1

2mterminals

variables longest path length is m+2 Westart with a CNF grammar G=(V,T,P,S) such that L(G)=L-{}.

Let the grammar have mvariables.

Pick n = 2m.

Let |z| >n.

Now,we know that the parse tree forz has a path with at least m+1variablesbeacuse thelengthof thelongestpathm+2. There are only mdifferent variables, so among the lowest m+1variableson that path,we can find two nodesAiandAjwith the same label, say A.

Proofof the Pumping Lemma for CFLs

BBM401 Automata Theory and Formal Languages8

There are only mdifferent variables, so among the lowest m+1variableson that path,we can find two nodesAiandAjwith the same label, say A.

Proofof the Pumping Lemma for CFLs

BBM401 Automata Theory and Formal Languages9

m, there are at least m+1 occurrences of variables A0, A1,..., Akonthe path.

As there are only m different variables in V, at

least two of the last m + 1 variables on the path (that is, Ak-m through Ak, inclusive) must be the same variable.

Suppose Ai=Aj, where k-mi< j k.

Proofof the Pumping Lemma for CFLs

BBM401 Automata Theory and Formal Languages10

u v w x y Ai=A Aj=A |vwx| <2m= n because lowest m+1 variables chosen.

String wis the yield of the

subtree rooted at Aj(A).

Stringvwxis the yield of the

subtree rooted at Ai(A). uand yare portions of z that are to the left and rightofthe subtree rooted at Ai. z S

Sincethere are no unitproductions

Bothv andx be .

Proofof the Pumping Lemma for CFLs

pumpzerotimes

BBM401 Automata Theory and Formal Languages11

u v w x y A A S u y A S w uwy= uv0wx0y mustbe in thelanguage.

Proofof the Pumping Lemma for CFLs

pumptvice

BBM401 Automata Theory and Formal Languages12

u v w x y A A S u y A S w uvvwxxy= uv2wx2y mustbe in thelanguage. A A v vx x

Proofof the Pumping Lemma for CFLs

pumpthreetimes

BBM401 Automata Theory and Formal Languages13

u v w x y A A S u y A S wuvvvwxvxy= uv3wx3y mustbe in thelanguage. A A v vx x vx A

Proofof the Pumping Lemma for CFLs

pumpi times

BBM401 Automata Theory and Formal Languages14

u v w x y A A S u y A S w A A v vx x vx A

Thus, uviwxiywherei0

mustbe in thelanguage. In order to show that a language L is NOT a CFL using the PumpingLemma:

1.SupposeL werea CFL.

2.Thenthereis an integerngivenus bythepumpinglemma,which we do not

know, we must plan for any possible n.

3.Pick a string zwhich must be in L, it must be defined using nand|z| >n.

Tricky Part 1: You should find a string z so that you can create a contradiction in step 5. YOU CANNOT SELECT A SPECIFIC STRING.

4.Breakzinto uvwxy, subject only to the constraints that |vwx|n and vx.

5.Pickiand show that uviwxiyis NOT L in order to create a contradiction.

Tricky Part 2: You have to show that uviwxiyis NOT in L using only the constraints that |vwx|n and vx. You may need to look at more than one cases.

YOU CANNOT GIVE A SPECIFIC EXAMPLE.

6.Conclude that L is NOT a CFL.

quotesdbs_dbs22.pdfusesText_28

[PDF] cfo bonus structure

[PDF] cfo salary $100 million company

[PDF] cfo salary guide 2018

[PDF] cfo salary guide nz

[PDF] cfo salary nyc

[PDF] cfse calculation pdf

[PDF] cft book pdf

[PDF] cft chemistry pdf

[PDF] cft course pdf

[PDF] cft formulation pdf

[PDF] cft notes pdf

[PDF] cft theory pdf

[PDF] cg math 3

[PDF] cgc 3200

[PDF] cgc dx