[PDF] 1 Equivalence of Finite Automata and Regular Expressions 2

View - Download 1 Equivalence of Finite Automata and Regular Expressions 2

Previous PDF

Next PDF

1 Equivalence of Finite Automata and Regular Expressions

Finite Automata Recognize Regular Languages

Theorem 1.Lis a regular language i there is a regular expressionRsuch thatL(R) =Li there is a DFAMsuch thatL(M) =Li there is a NFANsuch thatL(N) =L. i.e., regular expressions, DFAs and NFAs have the same computational power. Proof.Given regular expressionR, will constructNFANsuch thatL(N) =L(R) GivenDFAM, will construct regular expressionRsuch thatL(M) =L(R)2 Regular Expressions to NFA

Regular Expressions to Finite Automata

:::to Non-determinstic Finite Automata Lemma 2.For any regexR, there is an NFANRs.t.L(NR) =L(R).

Proof Idea

We will build the NFANRforR, inductively, based on the number of operators inR, #(R). Base Case:#(R) = 0 means thatRis;;, ora(from somea2). We will build NFAs for these cases. Induction Hypothesis:Assume that for regular expressionsR, with #(R)< n, there is an

NFANRs.t.L(NR) =L(R).

Induction Step:ConsiderRwith #(R) =n. Based on the form ofR, the NFANRwill be built using the induction hypothesis.Regular Expression to NFA

Base Cases

IfRis an elementary regular expression, NFANRis constructed as follows. R=;q 0R=q 0R=aq 0q 1a 1

Induction Step: Union

CaseR=R1[R2

By induction hypothesis, there areN1;N2s.t.L(N1) =L(R1) andL(N2) =L(R2). Build NFAN s.t.L(N) =L(N1)[L(N2)q 0q 1q 11q 12q 2q 21

Figure 1: NFA forL(N1)[L(N2)Induction Step: Union

Formal Denition

CaseR=R1[R2

LetN1= (Q1;;1;q1;F1) andN2= (Q2;;2;q2;F2) (withQ1\Q2=;) be such thatL(N1) = L(R1) andL(N2) =L(R2). The NFAN= (Q;;;q0;F) is given by

Q=Q1[Q2[ fq0g, whereq062Q1[Q2

F=F1[F2

is dened as follows (q;a) =8

1(q;a) ifq2Q1

2(q;a) ifq2Q2

fq1;q2gifq=q0anda= ;otherwiseInduction Step: Union

Correctness Proof

Need to show thatw2L(N) iw2L(N1)[L(N2).

)w2L(N) impliesq0w!Nqfor someq2F. Based on the transitions out ofq0,q0!N q

1w!Nqorq0!Nq2w!Nq. Considerq0!Nq1w!Nq. (Other case is similar) This

meansq1w!N1q(asNhas the same transition asN1on the states inQ1) andq2F1. This meansw2L(N1). 2 (w2L(N1)[L(N2). Considerw2L(N1); case ofw2L(N2) is similar. Then,q1w!N1qfor someq2F1. Thus,q0!Nq1w!Nq, andq2F. This means thatw2L(N).Induction Step: Concatenation

CaseR=R1R2

By induction hypothesis, there areN1;N2s.t.L(N1) =L(R1) andL(N2) =L(R2)

Build NFANs.t.L(N) =L(N1)L(N2)q

1q 11q 12q 2q 21
Figure 2: NFA forL(N1)L(N2)Induction Step: Concatenation

Formal Denition

CaseR=R1R2

LetN1= (Q1;;1;q1;F1) andN2= (Q2;;2;q2;F2) (withQ1\Q2=;) be such thatL(N1) = L(R1) andL(N2) =L(R2). The NFAN= (Q;;;q0;F) is given by

Q=Q1[Q2

q0=q1 F=F2 is dened as follows (q;a) =8

1(q;a) ifq2(Q1nF1) ora6=

1(q;a)[ fq2gifq2F1anda=

2(q;a) ifq2Q2

;otherwiseInduction Step: Concatenation

Correctness Proof

Need to show thatw2L(N) iw2L(N1)L(N2).

3 w2L(N) iq0w!Nqfor someq2F=F2. The computation ofNonwstarts in a state of N

1(namely,q0=q1) and ends in a state ofN2(namely,q2F2). The only transitions from a state

ofN1to a state ofN2is from a state inF1which have-transitions toq2, the initial state ofN2.

Thus, we have

q

0=q1w!Nqwithq2F=F2

i

9q02F1:9u;v2: w=uvandq0=q1u!Nq0!Nq2v!Nq

This means thatq1u!N1q0(withq02F1) andq2v!N2q(withq2F2). Hence,u2L(N1) and v2L(N2), and sow=uv2L(N1)L(N2). Conversely, ifu2L(N1) andv2L(N2) then for some q

02F1andq2F2, we haveq1u!N1q0andq2v!N2q. Then,

q

0=q1u!Nq0!Nq2v!Nq

Thus,q0w=uv!Nqand souv2L(N).Induction Step: Kleene Closure

First Attempt

CaseR=R1

By induction hypothesis, there isN1s.t.L(N1) =L(R1)

Build NFANs.t.L(N) = (L(N1))q

0q 1q 2

Figure 3: NFA accepts (L(N1))+

Problem:May not accept! One can show thatL(N) = (L(N1))+.Induction Step: Kleene Closure

Second Attempt

CaseR=R1

By induction hypothesis, there isN1s.t.L(N1) =L(R1)

Build NFANs.t.L(N) = (L(N1))

4 q 0q 1q 2

Figure 4: NFA accepts(L(N1))

Problem:May accept strings that are not in (L(N1))!Example demonstrating the problem q 0q

10;110;1Figure 5: Example NFANq

0q

10;110;1Figure 6: Incorrect Kleene Closure ofN

L(N) = (0[1)1(0[1). Thus, (L(N))=[(0[1)1(0[1). The previous construction, gives an NFA that accepts 062(L(N))!Induction Step: Kleene Closure

Correct Construction

CaseR=R1

First buildN1s.t.L(N1) =L(R1)

GivenN1build NFANs.t.L(N) =L(N1)

5 qq 0q 1q 2 Figure 7: NFA forL(N1)Induction Step: Kleene Closure

Formal Denition

CaseR=R1LetN1= (Q1;;1;q1;F1) be such thatL(N1) =L(R1). The NFAN= (Q;;;q0;F) is given by

Q=Q1[ fq0gwithq062Q1

F=F1[ fq0g

is dened as follows (q;a) =8

1(q;a) ifq2(Q1nF1) ora6=

1(q;a)[ fq1gifq2F1anda=

fq1gifq=q0anda= ;otherwiseInduction Step: Kleene Closure

Correctness Proof

Let us begin by stating what our goal is. We would like to showw2L(N) iw2L. If we choose to prove this statement by induction, most induction proofs will fail because this statement is too weak to be established by induction. How we choose to strengthen it depends on what parameter we will choose to induct over. One possibility isjwj. If we do induction on the length ofw, then we need to strengthen the statement by saying which strings are accepted from any stateq2Q, and not just the initial stateq0as in the above statement. We can carry such a proof out, but it is long. We instead present a proof that does induction over a parameter dierent than length ofw, but before presenting this proof we need to introduce some notation and terminology that we will nd convenient. Observe that we constructNfromN1by adding some-transitions: one fromq0toq1, and others fromq2F1toq1. We will call these \new" transitions. Recall that an accepting computation is a sequence of steps starting from the initial stateq0and ending in some accept state, such that every step conforms to the transition relation. Let us call a computationas havingnnew steps, if exactlynsteps inare according to the new-transitions. For anyn, let us dene A n=fw2jwhas an accepting computation where exactlynnew transitions are usedg 6 Observe that ifwhas an accepting computation thenw2Anfor somen0. We will prove by induction onn, the following statement

8n2N: w2Aniw2Ln

Before proving the above stronger statement by induction, let us see how proving the above state- ment establishes the correctness of the construction. Supposew2Lthen (by denition of Kleene closure)w2Lifor somei2N. By the above statement, it would mean thatw2Ai. In other words,whas an accepting computation that uses exactlyinew transitions, which just implies that Nacceptsw. On the other hand, supposeNacceptsw. SinceNhas an accepting computation onw, it must have an accepting computation that uses exactlyinew transitions, for some value ofi. In other words,w2Ai. By the above statement that means thatw2Liwhich implies that w2L. Thus we can establish both sides of the correctness claim.

Let us now prove by induction onn

8n2N: w2Aniw2Ln

Base CaseFor this statement we need to establish two base cases: one whenn= 0 and the other whenn= 1. Case 1:Letn= 0. Since the only transition out of the initial stateq0is a new transition, w2A0means that the computation takes no steps and stays inq0. If the computation on whas no transition steps, it means thatw=and clearlyw2L0. On the other hand, if w2L0thenw=andNacceptswby taking no steps asq02F. Thus, we have established the base case forn= 0. Case 2:Letn= 1. Supposew2L, thenN1has an accepting computation. Thus, there isq2F1such thatq1w!N1q. Observe that since every transition ofN1is a transition of N(which is not new), andF1Fwe have the following accepting computation ofNwith exactly one new transition q

0!Nq1w!N1q

Thusw2A1. Conversely, supposew2A1. Again, the only transition out ofq0is a new transition. Thus the accepting computation ofNonwmust be of the form q

0!Nq1w!N1q

for someq2F1; the reason thatqmust be inF1is becauseq0(the only other accept state) has no incoming transitions. Thus,q1w!N1qforq2F1, which means thatwis accepted byN1, and from the fact thatL(N1) =L, we can conclude thatw2L=L1. We have, therefore, established the base case forn= 1. Ind. Hyp.Assume that for alli < n,w2Aiiw2Li, wheren >1. Ind. StepSupposew2Ln. Then there areu;vsuch thatw=uv,u2Ln1andv2L. By induction hypothesis, we haveu2An1. Now, sincen >1, the accepting computation onu must end in a stateq2F1(because once you leaveq0you can never get back to it). Moreover sincev2L, from the correctness ofN1, we haveq1v!N1q0for someq02F1. Putting all of this together we have the following accepting computation q

0u!Nq!Nq1v!N1q0

7 which has exactlynnew transitions. Thus,w2An. To prove the converse, supposew2An. Sincen >1, the accepting computation onwmust be of the form q

0u!Nq!Nq1v!N1q0

wherew=uv, andqandq0are some states inF1. Thus,u2An1. By induction hypothesis, we haveu2Ln1. From the correctness ofN1,q1v!N1q0forq02F1means thatv2L. Putting this together, we get thatw=uv2(Ln1)L=Ln.Regular Expressions to NFA

To Summarize

We built an NFANRfor each regular expressionRinductively WhenRwas an elementary regular expression, we gave an explicit construction of an NFA recognizingL(R) WhenR=R1opR2(orR= op(R1)), we constructed an NFANforR, using the NFAs for R

1andR2.Regular Expressions to NFA

An Example

Build NFA for (1[01)

N 00 N 11 N 0101
N 1[011 01 N (1[01)1 01

3 DFAs to Regular Expressions

DFA to Regular Expression

8 Given DFAM, will construct regular expressionRsuch thatL(M) =L(R).In two steps: {Construct a \Generalized NFA" (GNFA)Gfrom the DFAM {And then convertGto a regexR3.1 Generalized NFA

Generalized NFA

A GNFA is similar to an NFA, but:

{There is a single accept state which is not the start state. {The start state has no incoming transitions, and the accept state has no outgoing tran- sitions. These are \cosmetic changes": Any NFA can be converted to an equivalent NFA of this kind. {The transitions are labeled not by characters in the alphabet, but byregular expressions. Foreverypair of states (q1;q2), the transition fromq1toq2is labeled by a regular expression(q1;q2). {\Generalized NFA" because a normal NFA has transitions labeled by, elements in

(a union of elements, if multiple edges between a pair of states) and;(missing edges).Generalized NFA

Transition: GNFAnon-deterministicallyreads a block of characters from the input, chooses an edge from the current stateq1to another stateq2, and if the block of symbols matches the regex(q1;q2), then moves toq2. Acceptance:Gacceptswif there exists some sequence of valid transitions such that on

starting from the start state, and after nishing the entire input,Gis in the accept state.Generalized NFA: Example

9 q 0q 1q 20 100
0 10

10Figure 8: Example GNFAG

Accepting run ofGon 11110100 isq01!Gq111!Gq1101!Gq100!Gq2Generalized NFA: Denition Denition 3.A generalized nondeterministic nite automaton (GNFA) isG= (Q;;q0;qF;), where

Qis the nite set of states

is the nite alphabet q02Qinitial state qF2(Qn fq0g, a single accepting state : (Qn fqFg)(Qn fq0g)! R, whereRis the set of all regular expressions over the alphabet Generalized NFA: Denition Denition 4.For a GNFAM= (Q;;q0;qF;) and stringw2, we sayMacceptswi there existx1;:::;xt2and statesr0;:::;rtsuch that w=x1x2x3xt r0=q0andrt=qF for eachi2[1;t],xi2L((ri1;ri)),10

3.2 Converting DFA to GNFA

Converting DFA to GNFA

A DFAM= (Q;;;q0;F) can be easily converted to an equivalent GNFAG= (Q0;;q00;q0F;):

Q0=Q[ fq00;q0FgwhereQ\ fq00;q0Fg=;

(q1;q2) =8 :;ifq1=q00andq2=q0 ;ifq12Fandq2=q0FS faj(q1;a)=q2gaotherwiseq 00q 0Fq 0q 1q 2 Prove:L(G) =L(M).3.3 Converting GNFA to Regular Expression

GNFA to Regex

SupposeGis a GNFA with only two states,q0andqF.

ThenL(R) =L(G) whereR=(q0;qF).

How aboutGwith three states?q

0q 1q FR 4R 1R 3R 2q 0q

F(R4)[(R1R2R3)11

Plan: Reduce any GNFAGwithk >2 states to an equivalent GFA withk1 states.GNFA to Regex: Fromkstates tok1states

Denition 5(Deleting a GNFA State).Given GNFAG= (Q;;q0;qF;) withjQj>2, and any stateq2Qn fq0;qFg, dene GNFArip(G;q) = (Q0;;q0;qF;0) as follows:

Q0=Qn fqg.

For any (q1;q2)2Q0n fqFg Q0n fq0g(possiblyq1=q2), let

0(q1;q2) = (R1R2R3)[R4;

whereR1=(q1;q),R2=(q;q),R3=(q;q2) andR4=(q1;q2).GNFA to Regex: Fromkstates tok1states

Correctness

Proposition 6.For anyq2Qn fq0;qFg,Gandrip(G;q)are equivalent. Proof.LetG0=rip(G;q). We need to show thatL(G) =L(G0). We will prove this in two steps: we will showL(G)L(G0) and then showL(G0)L(G). L(G)L(G0):First we showw2L(G) =)w2L(G0).w2L(G) =) 9q0=r0;r1;:::;rt=qF andx1;:::;xt2such thatw=x1x2x3xtand for eachi,xi2L((ri1;ri)). We need to showy1;:::;yd2andq0=s0;s1;:::;sd=qFsuch thatw=y1yd, and for eachi,yi2L(0(si1;si)). Dene (s0=q0;:::;sd=qF) to be the sequence obtained by deleting all occurrences ofqfrom (r0=q0;r1;:::;rt=qF).

To formally deneyj, rst we deneas follows:

(j) =8 :0 ifj= 0 iif 0< (j1)< t;wherei= mini>(j1)(ri6=q) undened otherwise. The range ofis the set of indicesisuch thatri6=q. Letd= mink((k) =t). Then,sj=r(j), forj= 0;:::;d.

Now we deneyj=x(j1)+1x(j)forj= 1;:::;d

Theny1yd=x1xt=w.

We need to show thatyj2L(0(sj1;sj)) for allj. We consider the following cases forj: (j) =(j1) + 1 (i.e.,r(j1)+16=q). Thenyj=xiandsj1=ri1andsj=ri, where i=(j).yj=xi2L((ri1;ri))L(0(ri1;ri)) =L(0(sj1;sj)). 12 (j)> (j1) + 1 (i.e.,r(j1)+1=q). Thenyj=x`xiandsj1=r`1andsj=ri, where`=(j1) + 1 andi=(j). y =L((r`1;q)(q;q)i`(q;ri))

L((r`1;r`)(q;q)(q;ri))

L((sj1;q)(q;q)(q;sj))

L(0(sj1;sj))

Thusw2L(G0) as we set out to prove.

L(G0)L(G):Next we need to show thatw2L(G0) =)w2L(G).w2L(G0) =)

9q0=s0;s1;:::;sd=qFandy1;:::;yd2such thatw=y1y2y3ydand for eachj,yj2

L(0(sj1;sj)) =L(((sj1;q)(q;q)(q;ri))[(sj1;sj))

Deneas follows, forj= 0;:::;d:

(j) =8 :0 ifj= 0; (j1) + 1 ifyj2L((sj1;sj)) (j1) +u+ 2 otherwise, whereu= minv(yj2L((sj1;q)(q;q)v(q;sj)))

Lett=(d). Fori= 0;:::;tdenerias follows:

r(i) =( s jif there existsjsuch thati=(j); q otherwise. Finally, denexi(i= 1;:::;t) as follows: ifi=(j) andi1 =(j1), then letxi=yj. For otheri((j1)< i1< i(j) for somej), we haveyj2L((sj1;q)(q;q)u(q;sj)) whereu=(j)(j1)2. Therefore we can writeyj=x`x(j), where`=(j1) + 1, such thatx`2L((sj1;q)),x(j)2L((q;sj)) andx`+1;:::;x(j)12L((q;q)). Verify that allxi(i= 1;:::;t) are well-dened by this. With these denitions it can be easily veried thatx0xt=y0yd=wandxi2L((ri1;ri)).DFA to Regex: Summary Lemma 7.For every DFAM, there is a regular expressionRsuch thatL(M) =L(R). Any DFA can be converted into an equivalent GNFA. So letGbe a GNFA s.t.L(M) =L(G). For any GNFAG= (Q;;q0;qF;) withjQj>2, for anyq2Qn fq0;qFg,Gandrip(G;q) are equivalent.rip(G;q) has one fewer state thanG. So givenG, by applyingriprepeatedly (choosingqarbitrarily each time), we can get a GNFA G

0with two states s.t.L(G) =L(G0). Formally, by induction on the number of states inG.

For a 2-state GNFAG0,L(G0) =L(R), whereR=(q0;qF).

13

DFA to Regex: Example

q 1q 200
1 1

Figure 9: Example DFADq

1q 2q 0qquotesdbs_dbs14.pdfusesText_20

[PDF] equivalence of nfa and dfa ppt

[PDF] equivalence of regular grammar and finite automata

[PDF] équivalence québec

[PDF] er musician earplugs

[PDF] eragon 1 pdf

[PDF] eragon 3 brisingr pdf

[PDF] eragon 3 pdf deutsch

[PDF] eragon 3 pdf español

[PDF] eragon 3 pdf letöltés

[PDF] eragon 3 pdf romana

[PDF] eragon 4 pdf download deutsch

[PDF] eragon 4 pdf magyar

[PDF] eragon book 3 pdf

[PDF] eragon book 3 pdf download

[PDF] eragon book 4 free pdf