Introduction

In this chapter, we briefly sample a few additional topics in DFA, which are of interest.

Optimum DFA

It is possible to have more than one DFAs that accept the same language. Among these equivalent DFAs, it is often useful to find the smallest, i.e., the DFA with the minimum possible number of states. This is especially important, when DFAs are used for designing computer hardware circuits.

Definition

Minimisation/optimisation of a deterministic finite automaton refers to the detection of those states of a DFA, whose presence or absence in a DFA does not affect the language accepted by the automata.

The states that can be eliminated from automata, without affecting the language accepted

by automata, are:

1. ▪Unreachable or inaccessible states.

2. ▪Dead states.

3. ▪Non-distinguishable or indistinguishable state or equivalent states.

Unreachable States

These are the states that cannot possibly be reached from the initial state. Unreachable states of a DFA are not reachable from the initial state of DFA, by any possible input sequence.

EXAMPLE 6.1.1: (Unreachable states)

1. i. Here, state 5 is unreachable, from the initial state 0, with any input string (either b or a).

2. ii. Here, states q2 and q4 are unreachable, from the initial state q0, with any input string (0 or 1).

Dead State or Trap State

A state is dead, if it is not an accepting state and has no out-going transitions, except to itself. Alternatively, a dead state is a nonfinal state of a DFA, whose transitions on every input symbol terminates on itself.