[PDF] Non-regular languages PDF slides2.pdf

Pumping Lemma examples Theorem L = {0n1n : n ≥ 0} is not regular proof: let p be the There are other ways to prove languages are non-regular, which we

Proof: – Recall, a language is any (finite or infinite) set of (finite) strings – It turns

[PDF] 09 - Non-Regular Languages and the Pumping Lemma

09 - Non-Regular Languages and the Pumping Lemma Languages If a language is regular, then by definition there exists a DFA (or NFA) that describes it

[PDF] proving languages not regular using Pumping Lemma

The Pumping Lemma is used for proving that a language is not regular 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] 05 Nonregular Languages - CS:4330 Theory of Computation - UFMG

Example > L1 = {w w has an equal number of 0s and 1s} is not regular > L2 = { w w has Prove that a language A is not regular using the pumping lemma: 1

[PDF] Non-regular languages and the pumping lemma 1 The pumping

24 sept 2018 · 4 Proof of pumping lemma 5 More nonregular languages Given a regular language, we now know a method to prove that it is regular - simply

[PDF] CS 301 - Lecture 6 Nonregular Languages and the Pumping

Nonregular Languages and Pumping lemma for regular languages We say: L の regular Example }{ 1 ba L n = },{ 2 baab L = regular regular }{ 2 1 ab L

[PDF] Chapter Eleven: Non-Regular Languages

In this chapter, we will see that there are • There is a proof tool that is often used to prove languages non-regular: – the pumping lemma

[PDF] Non-regularity Examples

Prove that the language L1 = {0p p is a prime number} is non-regular Solution: For the sake of contradiction, assume that L1 is regular The Pumping Lemma

[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] Non-regular languages

Pumping Lemma examples Theorem L = {0n1n : n ≥ 0} is not regular proof: let p be the There are other ways to prove languages are non-regular, which we

[PDF] pumping length of regular language

[PDF] purdue owl apa citation

[PDF] purdue owl pdf apa

[PDF] purdue owl pdf citation apa

[PDF] pure gym partners

[PDF] purebasic a beginner 's guide to computer programming

[PDF] puregym acquires fitness world

[PDF] puregym investor relations

[PDF] push ios updates airwatch

[PDF] pypacker

[PDF] python 3.6 cookbook

[PDF] python 3d data visualization

[PDF] python class best practices

[PDF] python cloud compiler

[PDF] python csv reader ï»¿

Non-regular languages

Pumping Lemma:LetLbe a regular language.There existsan integerp(\pumping length") for whicheveryw2Lwithjwj p can be written as w=xyz such that1for everyi0,xyiz2L, and2jyj>0, and3jxyj p. Idea: ifLhas a DFA, then for every large enough word inL, its path in the state machine goes through a small cycle Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 1/68

Non-regular languages

Using the Pumping Lemma to proveLis not regular:assumeLis regularthen there exists a pumping lengthpselect a stringw2Lof length at leastpargue thatfor every wayof writingw=xyzthat satises (2)

and (3) of the Lemma, pumping onyyields a string not inL.contradiction. Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 2/68

Pumping Lemma examples

Theorem

L=f0n1n:n0gis not regular.proof:

letpbe the pumping length forLchoosew= 0p1p w= 000000000:::0|{z} p111111111:::1|{z} pw=xyz, withjyj>0 andjxyj p.Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 3/68

Pumping Lemma examples

3 possibilities for where pumpable block occurs:

w=00000|{z} x000|{z} y0:::0111111111:::1|{z} z w=000000000:::011|{z} x11111|{z} y11:::1|{z} z w=0000000|{z} x00:::011111|{z} y1111:::1|{z} zLast two cases are ruled out by fact that pumping lemma requiresjxyj pin rst case

1, pumping onygives a string not in languageL.1

indeed, also in other 2 casesPaul GoldbergIntro to Foundations of CS; slides 2, 2017-18 4/68

Pumping Lemma examples

Theorem

L=fw:whas an equal number of 0s and 1sgis not regular.Proof: letpbe the pumping length forLchoosew= 0p1p w= 000000000:::0|{z} p111111111:::1|{z} pw=xyz, withjyj>0 andjxyj p. Note thatyis a non-empty string of 0's, soxy2zis not inL. There are other ways to prove languages are non-regular, which we will go over in exercises. Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 5/68

Summary in terms of \Course Program"

Dened a simple programming model:Deterministic Finite

AutomataPositive results about this model:

The languages computed by this model areclosedunder union, concatenation, and star.A more powerful model, NFAs, recognizeexactly the same languages that DFAs do.A convenient syntax, Regular expressions, describeexactly the samelanguages that DFAs (and NFAs) recognize.Negative results: Some languages arenot regular. This can be proved using the Pumping Lemma.Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 6/68

A more powerful machine

limitation of FA related to fact that they can only \remember" a bounded amount of informationWhat is thesimplestalteration that adds unbounded

\memory" to our machine?Should be able to recognize, e.g.,f0n1n:n0g.Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 7/68

Pushdown Automata

Pushdown automata (PDAs) have the same expressive power as context-free grammars; the languages they accept arecontext-free languages.A pushdown automaton is like a NFA but with an additional \memory stack" which can hold sequences of symbols from a memory alphabet.Automaton scans an input from left to right - at each step it may push a symbol onto the stack, or pop the stack. It cannot read other elements of the stack.Start with empty stack; accept if at end of string state is in subset FQof accepting states and stack is empty. (alternative

denition:the stack need not be empty in order to accept.)Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 8/68

Pushdown Automata

denition:the stack need not be empty in order to accept.)Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 8/68

Pushdown Automata

denition:the stack need not be empty in order to accept.)Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 8/68

Pushdown Automata

denition:the stack need not be empty in order to accept.)Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 8/68

Transitions

notationP= (Q;;;;q0;F) where is stack alphabet andis transition function. Action taken by machine is allowed to depend on top element of stack, input letter being read, and state. Action consists of new state, and possibly push/pop the stack.

Formally:

:Q([ fg)([ fg)!P(Q([ fg)) i.e. for each combination of state, letter being read, and topmost stack symbol, we are given a set of allowable new states, and actions on stack. Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 9/68

For example:

(q;a;m) =f(q2;m2);(q3;m3)g means that in stateq, if you readawithmat top of stack, you may move to stateq2 and replacemwithm2. Alternatively you may move to stateq3 and replacemwithm3. (q;a;) =f(q2;m2)g means in stateqwith inputa, go to stateq2 and pushm2on top of stack. Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 10/68

Example: Palindromes

Input alphabet =fa;b;cg

Use stack alphabet =fa0;b0;c0g

statesQ=ff;sg(fis \reading rst half",sis \reading second half")

Initial statef.

Accepting statesF=fsg

Transitions:

(f;a;) =f(f;a0);(s;);(s;a0)g (f;b;) =f(f;b0);(s;);(s;b0)g (f;c;) =f(f;c0);(s;);(s;c0)g (s;a;a0) =f(s;)g;(s;b;b0) =f(s;)g;(s;c;c0) =f(s;)g; (anything else) =;Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 11/68

An Accepting Computationaabacabaa

P aabacabaa Pa' aabacabaa Pa' b' a' a' aabacabaa Pa' state fstate fchange to state sstate s Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 12/68 Example of adeterministicPDAConsider palindromes overfa;b;cgwhich contain exactly onec.

Use stack alphabetM=fa0;b0g

statesQ=ff;sg(fis \reading rst half",sis \reading second half")

Initial statef, accepting statesT=fsg

Transitions:

(f;a;) = (f;a0) (f;b;) = (f;b0) (f;c;) = (s;) (s;a;a0) = (s;) ;(s;b;b0) = (s;) ; (anything else) is undened (reject input). So, deterministic PDAs can recognise certain non-regular languages (but can't recognise all PDA languages) Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 13/68

Another deterministic example

PDA to recognise \well-formed" strings of parentheses A single states(accepting)Input alphabetf(;)gMemory alphabetfxg (s;(;) =f(s;x)g (s;);x) =f(s;)g CommentsThe number ofx's on the stack is the number of('s read so far minus number of)'s read.Exercise

Design a NPDA for the language

faibjck:i;j;k0andi=jori=kgPaul GoldbergIntro to Foundations of CS; slides 2, 2017-18 14/68

Results for NPDA

Closure properties

Languages are closed under: Union, Concatenation, Kleene Star But not, e.g. intersectionAlternative language-representation mechanism Recall Kleene's Theorem, N/DFA$regular expression... Similar result for NPDA:languages recognized by aNPDAare exactly the languages described bycontext-free grammars, and they are called the context-free languages.Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 15/68

Context-Free Grammars

Alphabet, a nite collection of symbolsSet ofvariables(also callednon-terminals), one of which is thestarting symbol(usually letterS).set ofrules(also calledproductions): a rule says that some variablemay be replaced2by some string of letters/variables.

Start with S, apply rules until a string in

results...2

wherever it occurs in a string, i.e. regardless of contextPaul GoldbergIntro to Foundations of CS; slides 2, 2017-18 16/68

Derivations in CFGs

A simple CFG

Alphabet0,1,2.

S!0S1 S!B

B!2A derivation

S)0S1)00S11)

000S111)

000B111)0002111Another derivation

S)B)2set of all strings generated using grammarGis thelanguage

of the grammarL(G).called aContext-free Language(CFL)Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 17/68

Example CFG

programming language syntax often described using CFGs (Backus-Naur formnotation often used), e.g. hstmti ! hif-stmti j hwhile-stmti j hbegin-stmti j hasgn-stmti hif-stmti !IFhbool-expriTHENhstmtiELSEhstmti hwhile-stmti !WHILEhbool-expriDOhstmti hbegin-stmti !BEGINhstmt-listiEND hstmt-listi ! hstmti j hstmti;hstmt-listi hasgn-stmti ! hvari:=harith-expri hbool-expri ! harith-expri hcompare-opi harith-expri hcompare-opi !j j j = harith-expri ! hvari j hconsti j(harith-expri harith-opi harith-expri) harith-opi !+j j j = hconsti !0j1j2j3j4j5j6j7j8j9 hvari !ajbjcj:::jxjyjzPaul GoldbergIntro to Foundations of CS; slides 2, 2017-18 18/68

CFG formal denition

Acontext-free grammaris a 4-tuple

(V;;R;S)

whereVis a nite set called thenon-terminals is a nite set (disjoint fromV) called theterminalsRis a nite set ofproductions(orrules) where each

production is a non-terminal and a string of terminals and

non-terminals.S2Vis thestart variable(or start non-terminal)Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 19/68

CFG formal denition

Supposeu,v,ware strings of non-terminals and terminals, and A!wis a production.\uAvyieldsuwv" notation:uAv)uwv also: \yields in 1 step" notation:uAv)1uwvin general: \yields inksteps" notation:u)kv meaning: there exists stringsu1;u2;:::uk1for which u)u1)u2):::)uk1)vnotation:u)vmeaning:9k0 and stringsu1;:::;uk1for which

u)u1)u2):::)uk1)vifu=S(the start symbol), the above is aderivation ofvThelanguage ofG, denotedL(G) is:

fw2:S)wgPaul GoldbergIntro to Foundations of CS; slides 2, 2017-18 20/68

One more example

arithmetic expressions using inx operators ,, parentheses and \atoms"xandy.A set of arithmetic expressions start symbol:E(no other variable symbols) alphabet:+,,(,),x,y

Rules:

E!EE E!E+E E!(E) E!x E!yTo see thatx(x+y)is in the language, n da derivation.

E)EE)E(E))E(E+E)

)x(E+E))x(x+E))x(x+y) notation:E)x(x+y)Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 21/68

NPDA, CFG equivalence

Theorem

a language L is recognized by a NPDAiL is described by a CFG.Must provetwodirections: ())Lis recognized by a NPDAimpliesLis described by a CFG. (()Lis described by a CFGimpliesLis recognized by a NPDA. To prove this equivalence, it's useful to dene some other mechanisms that turn out to have equivalent expressive power (rst: \Chomsky normal form" CFGs). Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 22/68

Chomsky Normal Form

A restricted form of CFG that's easier to work with:

Denition

In Chomsky normal form every production has form

1A!BC2S!(noteSis start symbol)3A!a

whereA,B,Care any non-terminals, andais any terminal.Theorem Every CFL is generated by a CFG in Chomsky Normal Form.

Proof:Transform any CFG into equivalent CFG in CNF. 4 steps:add a new start symbol, which can produce prior start

remove \-productions"A!eliminate \unit productions"A!Bconvert remaining rules into proper form Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 23/68 conversion to Chomsky Normal Form (general idea; some detail missing)

add a new start symbolS0: add productionS0!Sremove \-productions"A!for each production withAon RHS, add production with

A's removed: e.g. for each ruleR!uAv,addR!uv

rule may lter back to start symbol in doing this.eliminate \unit productions"A!Bfor each production withBon LHS:B!u,add rule

A!u(do this forA=Start symbolalso)

Note.In removing \-productions"A!if we had a production R!Awe create a new productionR!unless we already had removed such a production before. Thus the process of removing these productions terminates! Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 24/68 conversion to Chomsky Normal Form convert remaining rules into proper form replace production of form:

A!u1U2u3:::uk

with:

A!U1A1U1!u1

1!U2A2

2!U3A3U3!u3

A k1!Uk1UkUk!ukIntroduce new non-terminalsA

1:::Ak1and also

1;U3:::Ukfor everyterminal in RHS

for any nonterminal

on the RHS, likeU2,we don't need a newrule for it.Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 25/68

Implementing CFGs with an NPDA

New goal: Take aChomsky Normal FormCFG, simulate any leftmostderivation with aNPDAExample:

CNF CFG

for 0 n21nA!ZC Z!0 C!AD D!1

A!2Typical leftmost

derivation (with some steps skipped)

A)0C)0AD)

00CD)00ADD)

002DD)0021D

)00211Always a set of terminals followed by a set ofnonterminalsThink of an NPDA simulating this derivation where the terminals are the stu we've already read, the nonterminals are the stack (leftmost NT is the top of stack) Paul GoldbergIntro to Foundations of CS; slides 2, 2017-18 26/68

Target of translation: Variation on NPDAs

Slight variations of NPDAs have the same expressiveness: allow to do \push-and-swap", rather than either a push or aquotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] Non-regular languages

Non-regular languages

Non-regular languages

Pumping Lemma examples

Theorem

L=f0n1n:n0gis not regular.proof:

Pumping Lemma examples

3 possibilities for where pumpable block occurs:

1, pumping onygives a string not in languageL.1

Pumping Lemma examples

Theorem

Summary in terms of \Course Program"

AutomataPositive results about this model:

A more powerful machine

Pushdown Automata

Pushdown Automata

Pushdown Automata

Pushdown Automata

Transitions

Formally:

For example:

Example: Palindromes

Input alphabet =fa;b;cg

Use stack alphabet =fa0;b0;c0g

Initial statef.

Accepting statesF=fsg

Transitions:

An Accepting Computationaabacabaa

Use stack alphabetM=fa0;b0g

Initial statef, accepting statesT=fsg

Transitions:

Another deterministic example

Design a NPDA for the language

Results for NPDA

Closure properties

Context-Free Grammars

Start with S, apply rules until a string in

Derivations in CFGs

A simple CFG

Alphabet0,1,2.

B!2A derivation

S)0S1)00S11)

000S111)

000B111)0002111Another derivation

Example CFG

CFG formal denition

Acontext-free grammaris a 4-tuple

CFG formal denition

One more example

Rules:

E)EE)E(E))E(E+E)

NPDA, CFG equivalence

Theorem

Chomsky Normal Form

Denition

In Chomsky normal form every production has form

1A!BC2S!(noteSis start symbol)3A!a

A's removed: e.g. for each ruleR!uAv,addR!uv

A!u(do this forA=Start symbolalso)

A!u1U2u3:::uk

A!U1A1U1!u1

1!U2A2

2!U3A3U3!u3

1:::Ak1and also

1;U3:::Ukfor everyterminal in RHS

Implementing CFGs with an NPDA

CNF CFG

A!2Typical leftmost

A)0C)0AD)

00CD)00ADD)

002DD)0021D

Target of translation: Variation on NPDAs