Deterministic Finite Automata (DFA)

The word “deterministic” refers to the fact that the transition is deterministic. There is only one state to which an automaton can transit from the current state each input. The word “finite” implies that number of state are finite. A finite automata consists of five parts:

  1. 1. A finite set of states, represented as Q.
  2. 2. A finite set of alphabet, represented as Σ.
  3. 3. An initial state, represented as q0 .
  4. A set of accepting states. An accepting state or final state is for ‘Yes’ answer. It is a subset of Q and is represented as F.
  5. F ⊆ Q
  6. 5. A next state function or a transition function. Next state depends on the current state and the current input. It is a function from Q X Σ to Q. It is repesented as δ .

Definition of DFA

Finite automata,

M = (Q, Σ, δ, q0, F), where

Q is a set of states.
Σ is a set of alphabet.
q0 ϵ Q is the initial state
F ⊆ Q is the set final states, and δ, the transition function, is a function from Q X Σ to Q.

Representation of a DFA

Let the machine M be a deterministic finite automata.

                M = {Q, Σ, δ, q0, F}, where

                Q = {q0, q1}

                Σ = (0, 1)

                F = {q1}.

q0 is the starting state and δ is the transition function as given below:

                δ(q0, 0) ⇒ q0
                δ(q0, 1) ⇒ q1
                δ(q1, 0) ⇒ q1
                δ(q1, 1) ⇒ q0 .

The above representation of transition function is not very readable. Conventionally, there are two representations for transition function:

  1. 1. State transition table. 2. State transition diagram.

State transition table

The transition table shows the state transition table of the transition function discussed in this section.

Deterministic Finite Automata - State transition table
State transition table
  • In the state transition table, there is a row for every state q1 ϵ Q.
  • In the state transition table, there is a column for every alphabet Ai ϵ Σ .
  • The starting state is marked as ‘‘.
  • The final state is marked as ‘*‘.

State transition diagram

The figure show the state transition diagram of the transition function discussed in this section.

Finite Automata - State transition diagram
State transition diagram

Language of the above DFA

It is easy to see that machine remain in same state on input 0.

The machine transitions from q0 to q1 and q1 to q0 , when the input is 1.

Machine will be in state q1 (final state). after reading odd number of 1’s.

Thus we can conclude that the DFA accepts a string if and only if the number of 1’s is odd.

The language L accepted by M, the given DFA, is the set of all string having odd number of 1’s.

Recommended:

  1. Automata Theory and Formal Languages
  2. Kleene Closure
  3. Recursive Definition of a Language
  4. Finite Representation of language
  5. Introduction to Finite Automata

Leave a Comment

Your email address will not be published. Required fields are marked *

x