Coupon Accepted Successfully!


Finite Automata

A finite automata is a 5-tuple (Q, Σ, δ, q0, F), where

  1. Q is a non-empty finite set called states.
  2. Σ is a non-empty finite set called alphabet.
  3. δ : Q × Σ Q is the transition function.
  4. q0   Q is the start state.
  5. F  Q is the set of accept states.

Non-Deterministic Finite Automata (NFA)

When the machine is in a given state and reads the next input symbol, we know the next state (using transition), i.e. it is determined. This is called deterministic computation. In a non-deterministic machine, several choices may exist for the next state at any point. Also, the automation can choose to make a transition from one state to another without reading any symbol. This type of transition is shown below.


Formally, a non-deterministic finite automation is a 5-tuple (Q, Σ, δ, q0, F), where

  1. Q is a non-empty finite set of states.
  2. Σ is a non-empty finite alphabet.
  3. δ: Q × Σε P(Q) is the transition function. Also, Q × Σ  2Q.
  4. q0   Q is the start state.
  5. F  Q is the set of accept states.

For example, NFA drawn below can be formally written as:–

  1. Q = {q1, q2, q3, q4}
  2. Σ = {0, 1}
  3. δ is given as


  1. ql is the start state.
  2. F = {q4}


Step of type (i): a


Step of type (i): b


Step of type (ii): a/b


Step of type (iv): (a/b)*


Step of type (iii): (a/b)*a


Figure 1 : Steps in constructing an NFAE for (a|b)*a

Some important points to remember

  1. Any DFA is also an NFA.
  2. For each NFA, there exist an equivalent DFA.
  3. Taking into account above two points, a language is regular if and only if some NFA recognizes it.
  4. If n is the number of states in NFA, then the equivalent DFA will have 2n state including φ state.

Converting NFA to DFA


Let’s have a look at the NFA(N) below that we will be converting in DFA(D).


To construct a DFA(D) that is equivalent to N, we first need to determine D’s states. Since N is having 3 states, D’s states will be 23 = 8. Now label each of D’s state with the subset of N’s state. Thus D’s state set is

{φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

The start state of D is the state that are reachable from 1 by travelling along ε arrows. An ε arrow goes from 1 to 3, so start state is {1, 3}. Accept states of D are the states containing N’s accept state, i.e. {{1}, {1, 2}, {1, 3}, {1, 2, 3}}.

Now, we determine D’s transition function. In D, state {2} goes to {2, 3} on input a, because in N, state Z goes to both 2 and 3 on input a and we can’t go farther from 2 or 3 along ε arrows. State {2} goes to {3} on input b. Similarly, state {1} goes to φ on input a, because no a arrows exit it in N. Continuing in this way, we obtain the diagram of D.

The above DFA can be simplified by removing the unwanted states. In this case, they are {1} and {1, 2} because there are no arrows pointing at these states and also none of them are start state and hence they can’t be reached. So, the simplified DFA will be



Test Your Skills Now!
Take a Quiz now
Reviewer Name