Deterministic Finite Automata - Chalmers

1 Deterministic Finite AutomataDefinition:A Deterministic Finite automaton (DFA) consists of1. a Finite set ofstates(often denotedQ)2. a Finite set ofsymbols(alphabet)3. atransition functionthat takes as argument a state and asymbol and returns a state (often denoted )4. astart stateoften denotedq05. a set offinaloracceptingstates (often denotedF)We haveq0 QandF Q1 Deterministic Finite AutomataSo a DFA is mathematically represented as a 5-uple(Q, , , q0, F)The transition function is a function inQ QQ is the set of 2-tuples (q, a) withq Qanda 2 Deterministic Finite AutomataHow to present a DFA? With atransition table01 q0q2q0 q1q1q1q2q2q1 The indicates thestartstate: hereq0 The indicates the final state(s) (here only one final stateq1)This defines the followingtransition diagramq001q210q10,13 Deterministic Finite AutomataFor this exampleQ={q0, q1, q2}start stateq0F={q1} ={0,1} is afunctionfromQ toQ :Q Q (q0,1) =q0 (q0,0) =q24 Example: passwordWhen does the automaton accepts a word?

2 ?It reads the word and accepts it if it stops in an accepting stateq0t6=tq1h6=hq2e6=eq3n6=nq4q5 Only the wordthenis acceptedHereQ={q0, q1, q2, q3, q4} is the set of all charactersF={q4}We have a stop or dead stateq5,notaccepting5 How a DFA Processes StringsLet us build an automaton that accepts the words that contain01as a subword ={0,1}L={x01y|x, y }We use the following statesA: startB: the most recent input was 1 (but not 01 yet)C: the most recent input was 0 (so if we get a 1 next we should goto the accepting state D)D: we have encountered 01 (accepting state)6We get the following automatonA10B10C10D0,1 Transition table01 ACBBCBCCD DDDQ={A,B,C,D}, ={0,1}, start state A, final state(s){D}7 Extending the Transition Function to StringsIn the previous example, what happens if we get 011? 100? 10101?We define (q, x) by induction :Q QBASIS (q, ) =qfor|x|= 0 INDUCTION supposex=ay(yis a string,ais a symbol) (q, ay) = ( (q, a), y)Notice that ifx=awe have (q, a) = (q, a) sincea=a and ( (q, a), ) = (q, a)8 Extending the Transition Function to Strings :Q QWe of (q, x)We can now define mathematically thelanguageaccepted by agiven automatonQ, , , q0, FL={x | F}On the previous example 100 is not accepted and 10101 is accepted9 MinimalisationThe same language may be represented by different DFAA10B10C10D0,1andA10B10C0,110 MinimalisationLater in the course we shall show that there is onlyonemachinewith the minimum number of states (up to renaming of states)Furthermore, there is a (clever) algorithm which can find thisminimal automaton given an automaton for a language11 ExampleMnthe cyclic automaton withnstates on ={1}such thatL(Mn) ={1l|n divides l}12 Functional representation.

3 Version 1Q=A|B|CandE= 0|1 andW= [E]One functionnext:Q E Qnext(A,1) =A, next(A,0) =Bnext(B,1) =C, next(B,0) =Bnext(C, b) =COne functionrun:Q W Qrun(q, b:x) =run(next(q, b), x),run(q,[]) =qaccept x=f inal(run(A, x)) wheref inal A=f inal B=F alse, f inal C=T rue13 Functional representation: Version 2E= 0|1,W= [E]Three functionsFA, FB, FC:W BoolFA(1 :x) =FAx,FA(0 :x) =FBx,FA[] =F alseFB(1 :x) =FCx,FB(0 :x) =FBx,FB[] =F alseFC(1 :x) =FCx,FC(0 :x) =FCx,FC[] =T rueWe have amutual recursive definitionof 3 functions14 Functional representation: Version 3data Q = A | B | Cdata E = O | Inext :: Q -> E -> Qnext A I = Anext A O = Bnext B I = Cnext B O = Bnext C _ = Crun :: Q -> [E] -> Qrun q (b:x) = run (next q b) xrun q [] = q15 Functional representation: Version 3accept :: [E] -> Boolaccept x = final (run A x)final :: Q -> Boolfinal A = Falsefinal B = Falsefinal C = True16 Functional representation: Version 4We haveQ -> E -> Q ~ Q x E -> Q~ E -> (Q -> Q)17 Functional representation: Version 4data Q = A | B | Cdata E = O | Inext :: E -> Q -> Qnext I A = Anext O A = Bnext I B = Cnext O B = Bnext _ C = Crun :: Q -> [E] -> Qrun q (b:x) = run (next b q) xrun q [] = q18 Functional representation: Version 4-- run q [b1.]

4 ,bn] is-- next bn (next b(n-1) (.. (next b1 q)..))-- run = foldl next19A proof by inductionA very important result, quite intuitive, is the :for any stateqand any wordxandywe haveq.(xy) = ( ).yProof by induction onx. We prove that:for allqwe haveq.(xy) = ( ).y(notice thatyis fixed)Basis:x= thenq.(xy) = ( ).yInduction step: we havex=azand we assumeq .(zy) = (q .z).yfor allq 20 The other definition of Recall thata(b(cd)) = ((ab)c)d; we have two descriptions of wordsWe define (q, ) =qand (q, xa) = ( (q, x), a)Theorem:We (q, x) = (q, x)for allx21 The other definition of Indeed we have provedq. =qandq.(xy) = ( ).yAs a special case we haveq.(xa) = ( ).aThis means that we have two functionsf(x) = (x) = (q, x) which satisfyf( ) =g( ) =qandf(xa) =f(x).ag(xa) =g(x).aHencef(x) =g(x) for allxthat (q, x)22 Automatic Theorem Provingf(0) =h(0) = 0, g(0) = 1f(n+ 1) =g(n), g(n+ 1) =f(n), h(n+ 1) = 1 h(n)We havef(n) =h(n)We can prove this automatically using DFA23 Automatic Theorem ProvingWe have 8 states:Q={0,1} {0,1} {0,1}We have only one action ={1}and ((a, b, c), s) = (b, a,1 c)The initial state is (0,1,0) = (f(0), g(0), h(0))Then we have (0,1,0).

5 1n= (f(n), g(n), h(n))We check that all accessible states satisfya=c(that is, thepropertya=cis an invariant for each transition of the Automata )24 Automatic Theorem ProvingA more complex examplef(0) = 0f(1) = 1f(n+2) =f(n)+f(n+1) f(n)f(n+1)f(2) = 1f(3) = 0f(4) = 1f(5) = 1..Show thatf(n+ 3) =f(n) by usingQ={0,1} {0,1} {0,1}and the transition function (a, b, c)7 (b, c, b+c bc) with theinitial state (0,1,1)25 Product of automataHow do we representinteractionbetween machines?This is via theproductoperationThere are different kind of productsWe may then havecombinatorial explosion: the product ofnautomata with 2 states has 2nstates!26 Product of Automata (example)The product ofAp0p1Bp0p1andCp1p0Dp1p0isA, Cp0p1B, Cp0p1A, Dp0p1B, Dp0p1If we start fromA, Cand after the wordwwe are in the state A,Dwe know thatwcontains an even number ofp0s and odd number ofp1s27 Product of Automata (example)Model of a system ofusersthat have three states I(dle),R(equesting) and U(sing).

6 We have two users fork= 1 ork= 2 Each user is represented by a simple automatonrkikuk28 Product of Automata (example)The complete system is represented by the product of these twoautomata; it has 3 3 = 9 statesi1, i2r1, i2u1, i2i1, r2r1, r2u1, r2i1, u2r1, u2u1, u229 The Product ConstructionGivenA1= (Q1, , 1, q1, F1) andA2= (Q2, , 2, q2, F2) two DFAswith the same alphabet we can define the productA=A1 A2set of stateQ=Q1 Q2transition function (r1, r2).a= ( , )intial stateq0= (q1, q2)accepting statesF=F1 F230 The Product ConstructionLemma:(r1, r2).x= ( , )We prove this by inductionBASE:the statement holds forx= STEP:if the statement holds foryit holds forx=ya31 The Product ConstructionTheorem:L(A1 A2) =L(A1) L(A2)Proof:We have (q1, q2).x= ( , ) F2, that isx L(A1) andx L(A2)Example: letMkbe the cyclic automaton that recognizesmultiple ofk, such thatL(Mk) ={an|k divides n}, thenM6 M9'M18 Notice that 6 divideskand 9 divideskiff 18 dividesk32 Product of automataIt can be quite difficult to build Automata directly for theintersection of two regular languagesExample: build a DFA for the language that contains the subwordabtwice and an even number ofa s33 Variation on the productWe defineA1 A2asA1 A2but we change the notion ofaccepting state(r1, r2) accepting iffr1 F1orr2 F2 Theorem:IfA1andA2are DFAs, thenL(A1 A2) =L(A1) L(A2)Example: multiples of 3 or of 5 by takingM3 M534 ComplementIfA= (Q, , , q0, F) we define thecomplement AofAas theautomaton A= (Q, , , q0, Q F)Theorem:IfAis a DFA, thenL( A) = L(A)Remark.

7 We haveA A =A A 35 LanguagesGiven an alphabet Alanguageis simply asubsetof Common languages, programming languages, can be seen as sets ofwordsDefinition:A languageL isregulariff there exists a DFAA, on the same alphabet such thatL=L(A)Theorem:IfL1, L2are regular then so areL1 L2, L1 L2, L136 Remark: Accessible Part of a DFAC onsider the following DFAq010q101q200q301it is clear that it accepts the same language as the DFAq010q101which is theaccessible partof the DFAThe remaining states are not accessible from the start stateandcan be removed37 Remark: Accessible Part of a DFAThe setAcc={ |x }is the set ofaccessiblestates of the DFA (states that are accessiblefrom the stateq0)38 Remark: Accessible Part of a DFAP roposition:IfA= (Q, , , q0, F)is a DFA then andA = (Q Acc, , , q0, F Acc)is a DFA such thatL(A) =L(A ).Proof:It is clear thatA is well defined and thatL(A ) L(A).Ifx L(A) then we Fand Acc.

8 F Accandx L(A ).39 Automatic Theorem ProvingTake ={a, b}.DefineLset ofx such that anyainxis followed by abDefineL set ofx such that anybinxis followed by aaThenL L ={ }Intuitively ifx6= inLwe have.. a .. a .. b ..ifxinL we have.. b .. b .. a ..40 Automatic Theorem ProvingWe should haveL L ={ }since a nonempty word inL L should be infiniteWe can prove this automatically with Automata !Lis regular: write a DFAAforLL is regular: write a DFAA forLWe can then computeA A and check thatL L =L(A A ) ={ }41 Application: control systemWe have several machines working concurrentlyWe need to forbid some sequence of actions. For instance, if wehave two machines MA and MB, we may want to say that MBcannot be on when MA is on. The alphabets will contain: onA,offA, onB, offBBetween onA, on2 there should be at least one offAThe automaton expressing this condition isp0onBonA6=onA,onBp1offAonB6=onB,offAp3 offBonAp242 Application: control systemWhat is interesting is that we can use the product construction tocombine several conditionsFor instance, another condition maybe that onA should appearbefore onB appear.

9 One automaton representing this condition isq0onA6=onA,onBonBq1q2We can take the product of the two Automata to express the twoconditions as one automaton, which may represent the controlsystem43