1.3.1 deterministic finite automaton

What is DFA?
Definition of DFA.
Different representation of DFA.
some problems in DFA

1. Deterministic Finite Automaton (DFA) Sampath Kumar S, AP/CSE, SECE

2. Deterministic Finite Automaton (DFA) In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called  Deterministic Automaton.   As it has a finite number of states, the machine is called  Deterministic Finite Machine  or  Deterministic Finite Automaton. 7 July 2017 2

3. Formal definition of DFA: A DFA can be represented by a 5-tuples (Q, ∑, δ, q , F) where − Q   is a finite set of states. ∑  is a finite set of symbols, called the  alphabet  of the automaton. δ is the transition function. q  is the initial state from where any input is processed (q  ∈ Q). F  is a set of final state/states of Q (F ⊆ Q). Note : δ is called Delta and ∑ is called Sigma 7 July 2017 3

4. Graphical Representation of a DFA A DFA is represented by digraphs called  state diagram or Transition Diagram . The vertices represent the states . The arcs labeled with an input alphabet show the transitions . The initial state is denoted by an empty single incoming arc . The final state is indicated by double circles . 7 July 2017 4

5. Transition Table: It is a tabular representation of a function like δ that takes 2 arguments and returns a value. The rows of the table correspond to the state and the columns correspond to the inputs. The entry for the row corresponding to state q and the column corresponding to input a is the state δ(q, a) 7 July 2017 5

6. Example Let a deterministic finite automaton be → Q = {a, b, c}, ∑ = {0, 1}, q ={a}, F ={c}, and Transition function δ as shown by the following table − 7 July 2017 6 Present State Next State for Input 0 Next State for Input 1 ->a a b b c a c* b c

7. Example Cont.., Its graphical representation would be as follows: Can you guess the language of above DFA? 7 July 2017 7

8. Extended Transition Function: Describes what happens when we start in any state and follow any sequence of inputs If δ is our transition function, then the extended transition function is denoted by δ * The extended transition function is a function that takes a state q and a string w and returns a state p (the state that the automaton reaches when starting in state q and processing the sequence of inputs w ) Formal definition : δ * ( q, ǫ) = q 7 July 2017 8

9. Problems to Discuses: Design DFA to accept string over ∑={0,1} with 2 consecutive 0’s . Construct a DFA that accepts all strings on ∑={0,1} except those contains substring 101. L= { w|w is of even length and begins with 01 over ∑={0,1} }. Give DFA accepting the string starting with substring 101 over ∑={0,1} Design DFA to accept string contain number of 1’s is in multiples of 3 over ∑={0,1}. Design DFA to accept string contain number of 1’s is not in multiples of 3 over ∑={0,1}. 7 July 2017 9

10. Problems (Cont..,): Construct a DFA that accepts all strings on ∑={0,1} that contain exactly 4 zeros. Construct a DFA over ∑={ a,b } where the number of b’s is divisible by 3. Construct a DFA that accepts even binary numbers on ∑={0,1} . Construct a DFA that accepts odd binary numbers on ∑={0,1} . 7 July 2017 10

11. 7 July 2017 11

12. நன்றி  7 July 2017 12