Finite Automata: Finite Automata
What is Finite Automata?: Finite Automata 1 What is Finite Automata? No temporary storage Input file cannot be re-written Only finite amount of information can be retained in the control unit Current state that the unit is in Can only deal with cases in which information to be maintained at any point in time is strictly bounded
Deterministic Finite Accepters: Finite Automata 2 Deterministic Finite Accepters Definition 2.1 A Deterministic Finite Accepter (DFA) is defined by the quintuple M = ( Q , , , q 0 , F ) where Q is a finite set of internal states is a finite set of symbols called input alphabet : Q Q is a total function called transition function q 0 Q is the initial state F Q is a set of final states
Example 2.1: Finite Automata 3 Example 2.1 M = ({ q 0 , q 1 , q 2 }, {0, 1}, , q 0 , { q 1 }) where ( q 0 , 0) = q 0 , ( q 0 , 1) = q 1 , ( q 1 , 0) = q 0 , ( q 1 , 1) = q 2 , ( q 2 , 0) = q 2 , ( q 2 , 1) = q 1 ,
Extended transition function: Finite Automata 4 Extended transition function Extended transition function , * can be defined recursively as * ( q , ) = q , * ( q , wa ) = ( * ( q , w ), a ) for all q Q , w * , a Try to verify that * ( q 0 , ab ) = q 2 when ( q 0 , a ) = q 1 and ( q 1 , b ) = q 2
Languages of DFA: Finite Automata 5 Languages of DFA Definition 2.2 The language accepted/recognized by a DFA M = ( Q , , , q 0 , F ) is the set of all strings on accepted by M L ( M ) = { w * | *( q 0 , w ) F } The complement L ( M ) = { w * | *( q 0 , w ) F }
Example 2.2: Finite Automata 6 Example 2.2 A DFA can be represented by a transition graph whose vertices represent states and edges represent transitions L ( M ) = { a n b | n 0}
Transition function in a table form: Finite Automata 7 Transition function in a table form
Example 2.3: Finite Automata 8 Example 2.3 A DFA that accepts all string on = { a , b } starting with prefix ab
Example 2.4: Finite Automata 9 Example 2.4 A DFA that accepts all string on = {0, 1} except those containing substring 001
Transition Graph: Finite Automata 10 Transition Graph Theorem 2.1 Let M = ( Q , , , q 0 , F ) be a deterministic finite accepter, and let G M be its associated transition graph. Then, for every q i , q j Q , and w + , * ( q i , w ) = q j if and only if there is in G M a walk with label w from q i to q j . Proof idea By induction on the length of the string, assuming that the claim is true for all strings v of length | v | n , then prove for any w of length | w | = n + 1; w = va . Note that the claim is obviously true for the basis case where n = 1.
Regular languages: Finite Automata 11 Regular languages Definition 2.3 A language L is called regular if and only if there exists some deterministic finite accepter M such that L = L ( M )
Example 2.5: Finite Automata 12 Example 2.5 Show that L = { awa | w { a , b } * } is regular
Example 2.6: Finite Automata 13 Example 2.6 For L from the previous example, show that L 2 is regular L 2 = { aw 1 aaw 2 a | w 1 , w 2 { a , b } * }
Nondeterministic Finite Accepters: Finite Automata 14 Nondeterministic Finite Accepters Definition 2.4 A Nondeterministic Finite Accepter (NFA) is defined by the quintuple M = ( Q , , , q 0 , F ) where Q is a finite set of internal states is a finite set of symbols called input alphabet : Q ( {}) 2 Q is a total function called transition function q 0 Q is the initial state F Q is a set of final states
Differences between NFA and DFA: Finite Automata 15 Differences between NFA and DFA The range of transition function , is in the powerset 2 Q , i.e. the value is a subset of Q ; not just a single element Empty string, is allowed as the second argument of , hence, NFA can make a transition without consuming an input symbol at all ( q i , a ) may yield an empty set, i.e. no transition is defined in this case An NFA accepts a string if there is at least one walk to a final state with the string even when some other walks by the same string lead to non-final states
Examples: Finite Automata 16 Examples An NFA can also be represented as a transition graph; an edge ( q i , q j ) is with a label a if and only if ( q i , a ) contains q j
Extended transition function for NFA: Finite Automata 17 Extended transition function for NFA * ( q i , w ) = Q j Q j is the set of all possible states, the NFA can be in having started at state q i and read w Definition 2.5 For an NFA, the extended transition function is defined so that * ( q i , w ) contains q j if and only if there is a walk in the transition graph from q i to q j labeled w . This holds for all q i , q j Q and w * .
Example 2.9: Finite Automata 18 Example 2.9 * ( q 1 , a ) = { q 0 , q 1 , q 2 } * ( q 2 , ) = { q 0 , q 2 } * ( q 2 , aa ) = { q 0 , q 1 , q 2 }
Languages of NFA: Finite Automata 19 Languages of NFA Definition 2.6 The language L accepted/recognized by an NFA M = ( Q , , , q 0 , F ) is defined as the set of all strings accepted . L ( M ) = { w * | * ( q 0 , w ) F } That is, the language consists of all strings w for which there is a walk labeled w from the initial vertex of the transition graph to some final vertex.
Example 2.10: Finite Automata 20 Example 2.10 L = {(10) n | n 0} Observe that * ( q 0 , 110) =
Why nondeterminism?: Finite Automata 21 Why nondeterminism? Non deterministic algorithms can serve as models for search-and-backtrack (deterministic) algorithms, e.g. for game playing programs Nonderterminism sometimes makes problem solving easy , e.g. when encountering a language which is a product of union such as { a 3 } { a 2 n | n 1} Nondeterminism is an effective mechanism for describing some complicated language concisely , e.g. S aSb | Certain theoretical results can be more easily established for NFA than for DFA
Equivalence of NFA and DFA?: Finite Automata 22 Equivalence of NFA and DFA? They are equivalent ! We can use nondeterminism to simplify formal arguments without loss of generality ! Let’s prove it; but first let’s define equivalence Definition 2.7 Two finite accepters M 1 and M 2 are said to be equivalent if L ( M 1 ) = L ( M 2 ), i.e. if both accept/recognize the same language.
Example of equivalence: Finite Automata 23 NFA DFA Both accept {(10) n | n 0} Example of equivalence
Power of models: Finite Automata 24 Power of models It is what a model can do A kind of automata is said to be “ more powerful ” than another kind if it can do something the other cannot! Obviously, NFA can do whatever DFA can since DFA is simply a restricted version of NFA On the other hand, for a given NFA is there always some DFA that accept/recognize the same language?
Converting NFA to equivalent DFA: Finite Automata 25 Converting NFA to equivalent DFA Label states of DFA with subsets of Q of NFA; for | Q | states there 2 |Q| subsets, i.e. finite number of states for the DFA When there is no specific transition in NFA for any input, make it go to a (non-final) trap state labeled with in DFA All other transitions in DFA are referenced back from the original NFA Any state in DFA that includes a final state of NFA must be made a final state
Example of (simplified) conversion: Finite Automata 26 Example of (simplified) conversion NFA DFA
Converting NFA to DFA: Finite Automata 27 Converting NFA to DFA Theorem 2.2 Let L be the language accepted/recognized by a nondeterministic finite accepter M N = ( Q N , , N , q 0 , F N ). Then there exists a deterministic finite accepter M D = ( Q D , , D , { q 0 }, F D ) such that L = L ( M D ). Proof idea Use the procedure NFA-to-DFA to construct transition graph G D of M D from the given M N . Observe that every vertex of GD must have exactly || outgoing edges, each labeled with a different symbol of .
Procedure NFA-to-DFA: Finite Automata 28 Procedure NFA-to-DFA Create a graph G D with vertex { q 0 }. Identify this vertex as the initial vertex . Repeat the following steps until no edges are missing Take any vertex { q i , q j , …, q k } of G D that has no outgoing edge for some a . Compute N * ( q i , a ), N * ( q j , a ), …, N * ( q k , a ). If N * ( q i , a ) N * ( q j , a ) … N * ( q k , a ) = { q l , q m , …, q n }, create a vertex for G D labeled { q l , q m , …, q n } if it does not already exists. Add to G D an edge from { q i , q j , …, q k } to { q l , q m , …, q n } and label it with a . Every sate of G D whose label contains any q f F N is identified as a final vertex . If M N accepts , the vertex { q 0 } in G D is also made a final vertex .
Further on the proof idea (1): Finite Automata 29 Further on the proof idea (1) G D has at most 2 | Q N | | | edges, the procedure always terminate Induction on the length of input string can be used to show that the construction gives the correct answer Assume any v of length | v | n , the presence of a walk labeled v from q 0 to q i in G N implies that there is a walk labeled v from { q 0 } to a state Q i = {…, q i , …} in G D For any w = va and a walk in G N labeled w from q 0 to q l ; there must be a walk labeled v from q 0 to q i and an edge (or sequence of edges) labeled a from q i to q l By inductive assumption , there will be a walk labeled v from { q 0 } to Q i ; and, by construction , there will be an edge from Q i to some state containing q l in its label
Further on the proof idea (2): Finite Automata 30 Further on the proof idea (2) The claim is obviously true for the basis case n = 1 The result is then whenever N * ( q 0 , w ) contains a final state q f , so does the label of the state yielded by D * ( q 0 , w ) The claim can then be reversed and respectively proved to show that if the label of D * ( q 0 , w ) contains q f , so must the state yielded by N * ( q 0 , w )
Regular languages and NFA: Finite Automata 31 Regular languages and NFA Consequently, a language L is called regular if and only if there exists some nondeterministic finite accepter M that accepts/recognizes L .
Example 2.13: Finite Automata 32 Example 2.13
States of equivalent DFA’s: Finite Automata 33 States of equivalent DFA’s A DFA defines a unique language But, a language may be accepted/recognized by many DFA’s
Indistinguishable/Distinguishable states: Finite Automata 34 Indistinguishable/Distinguishable states Definition 2.8 Two states p and q of a DFA are called indistinguishable if * ( p , w ) F implies * ( q , w ) F , and * ( p , w ) F implies * ( q , w ) F , for all w * . If, on the other hand, there exists some string w * such that * ( p , w ) F and * ( q , w ) F , or vice versa, then the states p and q are said to be distinguishable by a string w .
Finding distinguishable states: procedure mark: Finite Automata 35 Finding distinguishable states: procedure mark Remove all inaccessible states. Can be done by enumerating all simple paths from q 0 , any state that is not part of some path is inaccessible. Consider all pairs of states ( p , q ) if p F and q F or vice versa, mark the pair ( p , q ) as distinguishable. Repeat the following step until no previously unmarked pairs are marked. For all pairs ( p , q ) and all a , compute ( p , a ) = p a and ( q , a ) = q a . If the pair ( p a , q a ) is marked as distinguishable, mark ( p , q ) as distinguishable.
Procedure mark: the theorem: Finite Automata 36 Procedure mark: the theorem Theorem 2.3 The procedure mark , when applied to any DFA M = ( Q , , , q 0 , F ), terminates and determines all pairs of distinguishable states Proof idea The procedure obviously terminates and states of any pair marked are distinguishable Need to further show that the procedure finds all distinguishable pairs! Observe that when Step 3 terminates all states distinguishable by strings of length n -1 would have been marked; since there are no further states distinguishable by strings of length n , there will be no further distinguishable states by strings of length longer than n .
Example 2.15: Finite Automata 37 Example 2.15 Initial two equivalence classes are { q 0 , q 1 , q 3 } and { q 2 , q 4 } Applications of Step 3 split the equivalence classes into { q 0 }, { q 1 , q 3 }, { q 2 } and { q 4 } (try use 0 as an input symbol to check the transitions)
Reducing the number of states: procedure reduce: Finite Automata 38 Reducing the number of states: procedure reduce Given a DFA M = ( Q , , , q 0 , F ), we can construct a reduced DFA M ’ = ( Q ’, , ’, q 0 ’, F’ ) as follows. Use procedure mark to generate the equivalence classes say { q i , q j , …, q k } For each set { q i , q j , …, q k } of such indistinguishable states, create a state labeled ij…k for M ’. For each transition rule of M of the form ( q r , a ) = q p , find the sets to which q r and q p belong. If q r { q i , q j , …, q k } and q p { q l , q m , …, q n }, add to ’ a rule ’( ij…k , a ) = lm…n . The initial state q 0 ’ is that state of M ’ whose label includes the 0. F ’ is the set of all states whose label contains i such that q i F .
Example 2.16: Finite Automata 39 Example 2.16
Procedure reduce: the theorem (1): Finite Automata 40 Procedure reduce: the theorem (1) Theorem 2.4 Given any DFA M , application of the procedure reduce yields another DFA M ’ such that L ( M ) = L ( M ’) Further more M ’ is minimal in the sense that there is no other DFA with a smaller number of states which also accepts L ( M ). Proof idea There are two parts Showing that DFA created by reduce is equivalent to the original DFA by induction similar to the case for the equivalence of NFA and DFA Showing that M ’ is minimal by assuming that there is M 1 with fewer states than M ’ and equivalent to M ’, then produce a contradiction !
Procedure reduce: the theorem (2): Finite Automata 41 Procedure reduce: the theorem (2) Since there are no inaccessible states in M ’, there must be distinct strings w 1 , w 2 , …, w m such that ’ * ( p 0 , w i ) = p i , i = 1, 2, …, m Since M 1 has fewer states than M ’, there must be at least two of those strings, say w k and w l , such that 1 * ( q 0 , w k ) = 1 * ( q 0 , w l ) Since p k and p l are distinguishable , there must be some string x such that ’ * ( p 0 , w k x ) = ’ * ( p k , x ) is a final state, and ’ * ( p 0 , w l x ) = ’ * ( p l , x ) is a non final state (or vice versa) But, 1 * ( q 0 , w k x ) = 1 * ( 1 * ( q 0 , w k ), x ) = 1 * ( 1 * ( q 0 , w l ), x ) = 1 * ( q 0 , w l x ) Hence, M 1 either accepts both w k x and w l x or rejects both; a contradiction (to M ’)!