[PDF] [PDF] Finite Automata

Finite State Automata and Regular Languages

Finite-state automata or finite automata for short, are the simplest automata (see Fig Definition 3 7 A deterministic finite automaton (DFA), denoted by M, is

[PDF] Finite-state automata - Jeff Erickson

and that transitions among those states based on sequence of input symbols Finite-state machines are also known as deterministic finite-state automata, 

[PDF] Finite-State Automata and Algorithms

Finite-state automata (FSA) – What for? – Recap: Chomsky hierarchy of grammars and languages – FSA, regular languages and regular expressions

[PDF] Finite Automata

Finite State Automata (FSA) Deterministic On each input there is one and only one state to which the automaton can transition from its current state

[PDF] Finite State Automata and Image Recognition - CEUR-WSorg

We assume that the reader is familiar with the elementary facts about finite automata and regular sets, see e g [4] A finite automaton is displayed by its diagram 

[PDF] Languages (Finite State Machines) Carol Zander

When they have a transition for every character in the input alphabet, they are called deterministic finite automata (DFA) Formally, a finite state automaton consists 

[PDF] Finite Automata

“Program” prescribes how symbols read affect current state Final state is state FA is in when finished read- ing the input string There are accept states (double 

[PDF] Finite State Automata and Regular Expressions - UW-Madison

10,5 Figure 13 1: The transition diagram for the vending machine M Before we define a finite state automaton more formally, let's see another example Example  

Mathematical logic and quantum finite state automata

computation, it is promising to study the relation between quantum finite-state automata and mathematical logic After a brief introduction to the connection 

[PDF] finland emergency medical services

[PDF] fintech 2019

[PDF] fintech in india

[PDF] fintech investment in india 2019

[PDF] fintech ranking

[PDF] fintech startups

[PDF] fip travel

[PDF] fipy: partial differential equations with python

[PDF] fir and iir filters pdf

[PDF] fir copy sample

[PDF] fir filter applications ppt

[PDF] fir filter design

[PDF] fir filter design matlab

[PDF] fir filter design based on fpga pdf

[PDF] fir filter design lecture notes pdf

Finite AutomataSITE : http://www.info.univ-tours.fr/˜mirian/ Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 1/35

Finite State Automata (FSA)

DeterministicOn each input there is one and only one state to which the automaton can transition from its current stateNondeterministicAn automaton can be in several states at once Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 2/35

Deterministic finite state automaton

1. A finite set ofstates, often denotedQ

2. A finite set ofinput symbols, often denotedΣ

3. Atransition functionthat takes as arguments a state and an input symbol and

returns a state.

The transition function is commonly denotedδ

Ifqis a state andais a symbol, thenδ(q,a)is a statep(and in the graph that represents the automaton there is an arc fromqtoplabeleda)

4. Astart state, one of the states inQ

5. A set offinal or acceptingstatesF(F?Q)

Notation: A DFAAis a tuple

A= (Q,Σ,δ,q0,F)

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 3/35

Other notations for DFAs

1. Transition diagrams

Each state is a nodeFor each stateq?Qand each symbola?Σ, letδ(q,a) =p

Then the transition diagram has an arc fromqtop, labeledaThere is an arrow to the start stateq0Nodes corresponding to final states are marked with doubled circle

2. Transition tablesTabular representation of a functionThe rows correspond to the states and the columns to the inputsThe entry for the row corresponding to stateqand the column

corresponding to inputais the stateδ(q,a) Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 4/35 Example: An DFA accepting strings with asubstring01

A= ({q0,q1,q2},{0,1},δ,q0,{q1})

where the transition functionδis given by the table 0 1 →q0 q2 q0 ? q 1 q1 q1 q 2 q2 q1

Start0 11

q

1q1q00 0,1

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 5/35

Extending the Transaction Function toStrings

The DFA define a language: the set of all strings that result ina sequence of state transitions from the start state to an accepting stateExtended transition function Describes what happens when we start in any state and follow any sequence of inputsIfδis our transition function, then the extended transition function is denoted by ˆδThe extended transition function is a function that takes a stateqand a stringwand returns a statep(the state that the automaton reaches when starting in stateqand processing the sequence of inputsw) Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 6/35 Formal definition of the extended transitionfunction Definition by induction on the length of the input string

Basis:ˆδ(q,?) =q

If we are in a stateqand read no inputs, then we are still in stateq Induction:Supposewis a string of the formxa; that isais the last symbol ofw, andx is the string consisting of all but the last symbol Then:

ˆδ(q,w) =δ(ˆδ(q,x),a)

To computeˆδ(q,w), first computeˆδ(q,x), the state that the automaton is in after

processing all but the last symbol ofwSuppose this state isp,i.e.,ˆδ(q,x) =pThenˆδ(q,w)is what we get by making a transition from statepon inputa- the

last symbol ofw Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 7/35

Example

Design a DFA to accept the language

L={w|whas both an even number of0and an even number of1} Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 8/35

The Language of a DFA

The language of a DFAA= (Q,Σ,δ,q0,F), denotedL(A)is defined by

L(A) ={w|ˆδ(q0,w)is inF}

The language ofAis the set of stringswthat take the start stateq0to one of the accepting states IfLis aL(A)from some DFA, thenLis aregular language Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 9/35

Nondeterministic Finite Automata (NFA)

A NFA has the power to be in several states at onceThis ability is often expressed as an ability to "guess" something about its inputEach NFA accepts a language that is also accepted by some DFANFA are often more succinct and easier than DFAsWe can always convert an NFA to a DFA, but the latter may have exponentially

more states than the NFA (a rare case)The difference between the DFA and the NFA is the type of transition functionδ

For a NFAδis a function that takes a state and input symbol as arguments (like the DFA transition function), but returns a set of zeroor more states (rather than returning exactly one state, as the DFA must) Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 10/35

Example: An NFA accepting strings that endin01

Nondeterministic automaton that accepts all and only the strings of0s and1s that end in 01

Start0 10,1

q 0q2q1 Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 11/35

NFA: Formal definition

A nondeterministic finite automaton (NFA) is a tupleA= (Q,Σ,δ,q0,F)where:

1.Qis a finite set ofstates

2.Σis a finite set ofinput symbols

3.q0?Qis thestart state

4.F(F?Q) is the set offinal or acceptingstates

5.δ, thetransition functionis a function that takes a state inQand an input symbol

inΔas arguments and returns a subset ofQThe only difference between a NFA and a DFA is in the type of value thatδreturns

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 12/35

Example: An NFA accepting strings that endin01

A= ({q0,q1,q2},{0,1},δ,q0,{q2})

where the transition functionδis given by the table 0 1 →q0 {q0,q1} {q0} q 1 {q2} ? q 2

Start0 10,1

q 0q2q1 Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 13/35

The Extended Transition Function

Basis:ˆδ(q,?) ={q}

Without reading any input symbols, we are only in the state webegan in

Induction:

Supposewis a string of the formxa; that isais the last symbol ofw, andxis the string consisting of all but the last symbolAlso suppose thatˆδ(q,x) ={p1,p2,...pk,}Let k[ i=1δ(pi,a) ={r1,r2,...,rm} Then:

ˆδ(q,w) ={r1,r2,...,rm}

We compute

ˆδ(q,w)by first computingˆδ(q,x)and by then following any transition from any of these states that is labeleda Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 14/35

Example: An NFA accepting strings that endin01

Start0 10,1

q

0q2q1Processingw= 00101

1.

ˆδ(q0,?) ={q0}

2.

ˆδ(q0,0) =δ(q0,0) ={q0,q1}

3. ˆδ(q0,00) =δ(q0,0)?δ(q1,0) ={q0,q1} ? ∅={q0,q1} 4. ˆδ(q0,001) =δ(q0,1)?δ(q1,1) ={q0} ? {q2}={q0,q2} 5. ˆδ(q0,0010) =δ(q0,0)?δ(q2,0) ={q0,q1} ? ∅={q0,q1} 6. ˆδ(q0,00101) =δ(q0,1)?δ(q1,1) ={q0} ? {q2}={q0,q2} Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 15/35

The Language of a NFA

The language of a NFAA= (Q,Σ,δ,q0,F), denotedL(A)is defined by

L(A) ={w|ˆδ(q0,w)∩F?=∅}

The language ofAis the set of stringsw?Σ?such thatˆδ(q0,w)contains at least one accepting state The fact that choosing using the input symbols ofwlead to a non-accepting state, or do not lead to any state at all, does not preventwfrom being accepted by a NFA as a whole. Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 16/35 Equivalence of Deterministic andNondeterministic Finite Automata Every language that can be described by some NFA can also be described by some DFA.The DFA in practice has about as many states as the NFA, although it has more transitions.In the worst case, the smallest DFA can have2n(for a smallest NFA withnstate). Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 17/35

Proof: DFA can do whatever NFA can do

The proof involves an important construction called subset construction because it involves constructing all subsets of the set of stages of NFA.

From NFA to DFA

We have a NFAN= (QN,Σ,δN,q0,FN)The goal is the construction of a DFAD= (QD,Σ,δD,{q0},FD)such that

L(D) =L(N).

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 18/35

Subset Construction

Input alphabets are the same.The start set inDis the set containing only the start state ofN.QDis the set of subsets ofQN,i.e.,QDis the power set ofQN.

IfQNhasnstatesQDwill have2nstates. Often, not all of these states are

accessible from the start state.FDis the set of subsetsSofQNsuch thatS∩FN?=∅. That is,FDis all sets of

N's states that include at least one accepting state ofN.For each setS?QNand for each input symbola?Σ

D(S,a) =[

p?Sδ

N(p,a)

To computeδD(S,a), we look at all the statespinS, see what statesNgoes frompon inputa, and take the union of all those states. Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 19/35

Example

Start0 10,1

q 0q2q1 (each one corresponding to a subset ofQN) 0 1 → {q0} {q0q1} {q0} {q1} {q2} ?{q2} {q0,q1} {q0q1} {q0,q2} ?{q0,q2} {q0q1} {q0} ?{q1,q2} {q2} ?{q0,q1,q2} {q0q1} {q0,q2} Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 20/35

Example: with new names

Note: The states of D correspond to subsets of states of N , butwe could have denoted the states of D by, say, A - F just as well. 0 1 A A A →B E B C A D ?D A A E E F ?F E B ?G A D ?H E F Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 21/35

Avoiding exponential blow-up

We can often avoid the exponential blow-up by constructing the transition table forD only for accessible states S as follows:

Basis:S={q0}is accessible inD

Induction: If stateSis accessible, so are the states in aS a?ΣδD(S,a). Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 22/35

Theorem

IfD= (QD,Σ,δD,{q0},FD)is the DFA constructed from NFA

N= (QN,Σ,δN,q0,FN)by the subset construction, thenL(D) =L(N)?Proof:First we show on an induction on|w|that

δD(({q0},w) =ˆδN(q0,w)Basis

:w=?. The claim follows from def.

Induction

:ˆδD({q0},x.a) =.... Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 23/35

Theorem

A languageLis accepted by some DFA if and only ifLis accepted by some NFA.Proof:The "if" part is the theorem before

For the "only if" part we note that any DFA can be converted to an equivalent NFA by modifying theδDtoδNby the rule

IfδD(q,a) =pthenδN(q,a) ={p}

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 24/35

Exponential Blow-Up

There is an NFANwithn+ 1states that has no equivalent DFA with fewer than2n states. q0q0q0q0q0 0,1

0,10,10,10,11

L(N): the set of all strings of0and1such that thenth symbolfrom the endis1.

L(N) ={x1c2c3...cn|x? {0,1}?,ci? {0,1}}

Suppose an equivalent DFADwith fewer than2nstates exists.

Dmust remember the lastnsymbols it has read.

There are2nbitsequencesa1a2...an

q?ˆδN(q0,b1b2...bn), a

1a2...an?=b1b2...bn

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 25/35

Exponential Blow-Up

Since the sequences are different, they must differ in some position, sayai?=bi

Case 1:i= 1

1a2...an

0b2...bn

Thenqhas to be both an accepting and a non accepting state.

Case 2:i >1

a

1...ai-11ai+1...an

b

1...bi-10bi+1...bn

Now ˆδN(q0,a1...ai-11ai+1...an0i-1) =ˆδN(q0,b1...bi-10bi+1...bn0i-1) and

ˆδN(q0,a1ai-11ai+1an0i-1)?FD

δN(q0,b1bi-10bi+1bn0i-1)??FD

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 26/35

Finite Automata with Epsilon-Transition

We allow now a transition on?,i.e., the empty stringA NFA is allowed to make a transition spontaneously, withoutreceiving an input

symbolThis capability does not expand the class of languages that can be accepted by finite automata, but it does give us some added programming convenience Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 27/35

Example

NFA that accepts decimal numbers consisting of: an optional+or-sign; a string of digits; a decimal point and another string of digits. Eitherthe first or the second string of bits can be empty, but at least one of the two strings must be nonempty. Start q 0q1q2 q 4q

3q5?,+,-0,1,...,9

0,1,...,90,1,...,90,1,...,9

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 28/35

Formal Notation

An?-NFAA= (Q,Σ,δ,q0,F)where all components have their same interpretation as for NFA, except thatδis now a function that takes arguments:

1. A state inQand

2. A member ofΣ? {?}

We require that?cannot be a member ofΣ

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 29/35

Epsilon-Closures

We define?-closureECLOSE(q)recursively, as follows:

Basis: Stateqis inECLOSE(q)

Induction: If statepis inECLOSE(q), and there is a transition fromptorlabeled?, thenris inECLOSE(q) More precisely, ifδis the transition function of the?-NFA involved, andpis in ECLOSE(q), thenECLOSE(q)also contains all the states inδ(p,?) Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 30/35

Extended Transitions and Languages for?-NFA

The definition ofˆδis :

Basis

ˆδ(q,?) =ECLOSE(q)

If the label of the path is?, then we can follow only?-labeled arcs extending from stateq InductionSupposewis of the formxa, wherea?Σis the last symbol ofw. We compute

ˆδ(q,w)as follows:

1. Let{p1,p2,...pk}beˆδ(q,x)

Thepiare all and only the states that we can reach fromqfollowing a path labeledx. This path may end with one or more?-transitions and may have other ?-transitions.

2. Let

Ski=1δ(pi,a)be the set{r1,r2,...,rm}

Follow all transitions labeledafrom states we can reach fromqalong paths labeledx. Therjare some of the states we can reach fromqalong paths labeledw. The additional states we can reach are found from therjby thequotesdbs_dbs20.pdfusesText_26