DMIoT School of Computing Software Eng’g Ac/Program

CHAPTER TWO
2. FINITE AUTOMATA
2.1. Introduction
Our introduction in the first chapter to the basic concepts of computation, particularly the
discussion of automata, is informal. At this point, we have only a general understanding of what
an automaton is and how it can be represented by a graph. To progress, we must be more precise,
provide formal definitions, and start to develop rigorous results. We begin with finite accepters,
which are a simple, special case of the general scheme introduced in the last chapter. This type of
automaton is characterized by having no temporary storage. Since an input file cannot be rewritten,
a finite automaton is severely limited in its capacity to “remember” things during the computation.
A finite amount of information can be retained in the control unit by placing the unit into a specific
state. But since the number of such states is finite, a finite automaton can only deal with situations
in which the information to be stored at any time is strictly bounded.

2.2. Deterministic Finite Automata

Finite Automaton (also known as finite accepters) can be classified into two types:
 Deterministic Finite Automaton (DFA)
 Non-deterministic Finite Automaton (NDFA / NFA)

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.

In common with all automata, a deterministic automata has internal states, rules for transitions
from one state to another, some input, and ways of making decisions. All of these are incorporated
in the following definition.

A DFA can be represented by a 5-tuple (Q, Σ, δ, q0, F) where:

 Q is a finite set of states.

 Σ is a finite set of symbols called the alphabet.
 δ is the transition function where δ: Q × Σ → Q
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).

Formal Languages and Automata Theory (SEng3042) Page 1

DMIoT School of Computing Software Eng’g Ac/Program

A deterministic finite automata operates in the following manner. At the initial time, it is assumed
to be in the initial state q0, with its input mechanism on the leftmost symbol of the input string.
During each move of the automaton, the input mechanism advances one position to the right, so
each move consumes one input symbol. When the end of the string is reached, the string is accepted
if the automaton is in one of its final states. Otherwise the string is rejected. The input mechanism
can move only from left to right and reads exactly one symbol on each step. The transitions from
one internal state to another are governed by the transition function δ. For example, if
δ (q0, a) = q1,
then if the DFA is in state q0 and the current input symbol is a, the DFA will go into state q1.

In discussing automata, it is essential to have a clear and intuitive picture to work with. To
visualize and represent finite automata, we use transition graphs, in which the vertices represent
states and the edges represent transitions. The labels on the vertices are the names of the states,
while the labels on the edges are the current values of the input symbol. For example, if q0 and q1
are internal states of some DFA M, then the graph associated with M will have one vertex labeled
q0 and another labeled q1. An edge (q0, q1) labeled a represents the transition δ(q0, a) = q1. The
initial state will be identified by an incoming unlabeled arrow not originating at any vertex.
Final states are drawn with a double circle.

More formally, if M = (Q, Σ, δ, q0, F) is a deterministic finite automata, then its associated
transition graph GM has exactly |Q| vertices, each one labeled with a different qi ∈ Q. For every
transition rule δ (qi, a) = qj, the graph has an edge (qi, qj) labeled a. The vertex associated with q0
is called the initial vertex, while those labeled with qf ∈ F are the final vertices. It is a trivial
matter to convert from the (Q, Σ, δ, q0, F) definition of a DFA to its transition graph representation
and vice versa.

The graph in Figure 2.1 represents the DFA

M = ({q0, q1, q2},{0, 1}, δ, q0,{ql}),
where δ is given by
δ (q0, 0) = q0, δ (q0, 1) = q1,
δ (q1, 0) = q0, δ (q1, 1) = q2,
δ (q2, 0) = q2, δ (q2, 1) = q1.

This DFA accepts the string 01. Starting in state q0, the symbol 0 is read first. Looking at the edges
of the graph, we see that the automaton remains in state q0. Next, the 1 is read and the automaton

Formal Languages and Automata Theory (SEng3042) Page 2

 DMIoT School of Computing Software Eng’g Ac/Program

goes into state q1. We are now at the end of the string and, at the same time, in a final state q1.
Therefore, the string 01 is accepted. The DFA does not accept the string 00, since after reading two
consecutive 0’s, it will be in state q0. By similar reasoning, we see that the automaton will accept
the strings 101, 0111, and11001, but not 100 or 1100.

Figure-2.1: Transition Graph

It is convenient to introduce the extended transition function δ*: Q × ∑* → Q. The second

argument of δ* is a string, rather than a single symbol, and its value gives the state the automaton
will be in after reading that string. For example, if

δ(q0, a) = q1
and
δ(q1, b) = q2,
then
δ* (q0, ab) = q2.
Formally, we can define δ* recursively by
δ* (q, ε) = q, … (2.1)
δ* (q, wa) = δ(δ* (q, w), a), … (2.2)
for all q ∈ Q, w ∈ Σ*, a ∈ Σ. To see why this is appropriate, let us apply these definitions to the
simple case above. First, we use (2.2) to get
δ* (q0, ab) = δ(δ* (q0, a), b) … (2.3)
But
δ* (q0, a) = δ(δ* (q0, ε), a)
= δ(q0, a)
= q1
Substituting this into (2.3), we get
δ* (q0, ab) = δ(q1, b) = q2
as expected.

Formal Languages and Automata Theory (SEng3042) Page 3

 DMIoT School of Computing Software Eng’g Ac/Program

 Languages and DFA’s

The language accepted by a DFA M = (Q, Σ, δ, q0, F) is the set of all strings on Σ accepted by M.
In formal notation,
L(M) = {w ∈ Σ* : *(q0, w) ∈ F}
A DFA will process every string in Σ* and either accept it or not accept it. Non-acceptance means
that the DFA stops in a non-final state, so that
[L(M)]’ = {w ∈ Σ* :  *(q0, w) ∉ F}
Example:-
Consider the DFA in the following figure, Figure 2.2.
In drawing Figure 2.2 we allowed the use of two labels on a single edge. Such multiply labeled
edges are shorthand for two or more distinct transitions: The transition is taken whenever the input
symbol matches any of the edge labels.
The automaton in Figure 2.2 remains in its initial state q0 until the first b is encountered. If this is
also the last symbol of the input, then the string is accepted. If not, the DFA goes into state q2, from
which it can never escape. The state q2 is a trap state. We see clearly from the graph that the
automaton accepts all strings consisting of an arbitrary number of a's, followed by a single b. All
other input strings are rejected. In set notation, the language accepted by the automaton is
L = {anb: n ≥ 0}.

Figure-2.2
Exercise:- Find L’ of the above language.

Example:-
Find a deterministic finite accepter that recognizes the set of all strings on Σ = {a, b} starting with
the prefix ab.

The only issue here is the first two symbols in the string; after they have been read, no further
decisions are needed. Still, the automaton has to process the whole string before its decision is
made. We can therefore solve the problem with an automaton that has four states; an initial state,
two states for recognizing ab ending in a final trap state, and one non-final trap state. If the first
symbol is an a and the second is a b, the automaton goes to the final trap state, where it will stay

Formal Languages and Automata Theory (SEng3042) Page 4

DMIoT School of Computing Software Eng’g Ac/Program

since the rest of the input does not matter. On the other hand, if the first symbol is not an a or the
second one is not a b, the automaton enters the non-final trap state. The simple solution is shown in
Figure 2.3.

Figure-2.3
 Regular Languages
Every finite automaton accepts some language. If we consider all possible finite automata, we get
a set of languages associated with them. We will call such a set of languages a family. The family
of languages that is accepted by deterministic finite accepters is quite limited. The structure and
properties of the languages in this family will become clearer as our study proceeds; for the moment
we will simply attach a name to this family.

A language L is called regular if and only if there exists some deterministic finite accepter M such
that L= L(M).

Example-1:-
Show that the following language is regular.

L = {awa: w ∈ {a, b}* }

To show that this or any other language is regular, all we have to do is find a DFA for it. The
construction of a DFA for this language is similar to the above example (figure 2.3), but a little
more complicated.

What this DFA must do is check whether a string begins and ends with an a; what is between is
immaterial. The solution is complicated by the fact that there is no explicit way of testing the end
of the string. This difficulty is overcome by simply putting the DFA into a final state whenever the
second a is encountered. If this is not the end of the string, and another b is found, it will take the
DFA out of the final state. Scanning continues in this way, each a taking the automaton back to its
final state. The complete solution is shown in Figure 2.4.

Formal Languages and Automata Theory (SEng3042) Page 5

DMIoT School of Computing Software Eng’g Ac/Program

Figure-2.4

Again, trace a few examples to see why this works. After one or two tests, it will be obvious that
the DFA accepts a string if and only if it begins and ends with an a. Since we have constructed a
DFA for the language, we can claim that, by definition, the language is regular.

Example-2:-

Given a language L = {awa: w ∈ {a, b}*}. Show that L2 is regular language.

Again we show that the language is regular by constructing a DFA for it. We can write an explicit
expression for L2, namely

L2 = {aw1a aw2a: w1, w2 ∈ {a, b}*},

Therefore, we need a DFA that recognizes two consecutive strings of essentially the same form (but
not necessarily identical in value). The diagram in Figure 2.4 can be used as a starting point, but
the vertex q3 has to be modified. This state can no longer be final since, at this point, we must start
to look for a second substring of the form awa. To recognize the second substring, we replicate the
states of the first part (with new names), with q3 as the beginning of the second part. Since the
complete string can be broken into its constituent parts wherever aa occurs, we let the first
occurrence of two consecutive a’s be the trigger that gets the automaton into its second part. We
can do this by making δ(q3, a) = q4. The complete solution is in Figure 2.5. This DFA accepts L2,
which is therefore regular.

Formal Languages and Automata Theory (SEng3042) Page 6

 DMIoT School of Computing Software Eng’g Ac/Program

Figure-2.5

 This example suggests the conjecture that if a language L is regular, so are L2, L3,… .

2.3. Nondeterministic Finite Automata (NFA)

Nondeterminism means a choice of moves for an automaton. Rather than prescribing a unique move
in each situation, we allow a set of possible moves. Formally, we achieve this by defining the
transition function so that its range is a set of possible states.

Unlike DFA, NFA has a set of possible transitions from a state with an input.

A nondeterministic finite accepter or NFA is defined by the quintuple

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

where Q, Σ, q0, F are defined as for deterministic finite accepters, but  : Q X (Σ U { ε })  2Q

Note that there are three major differences between this definition and the definition of a DFA. In a
nondeterministic accepter, the range of δ is in the powerset 2Q, so that its value is not a single
element of Q but a subset of it. This subset defines the set of all possible states that can be reached
by the transition. If, for instance, the current state is q1, the symbol a is read, and

δ(q1, a) = {q0, q2} :

then either q0 or q2 could be the next state of the NFA. Also, we allow ε as the second argument of δ.
This means that the NFA can make a transition without consuming an input symbol. Although we
still assume that the input mechanism can only travel to the right, it is possible that it is stationary on

Formal Languages and Automata Theory (SEng3042) Page 7

 DMIoT School of Computing Software Eng’g Ac/Program

some moves. Finally, in an NFA, the set δ (qi, a) may be empty, meaning that there is no transition
defined for this specific situation.

Like DFA's, nondeterministic accepters can be represented by transition graphs. The vertices are
determined by Q, while an edge (qi, qj) with label a is in the graph if and only if δ (qi; a) contains qj.
Note that since a may be the empty string, there can be some edges labeled ε. A string is accepted by
an NFA if there is some sequence of possible moves that will put the machine in a final state at the
end of the string.

A string is rejected (that is, not accepted) only if there is no possible sequence of moves by which a
final state can be reached. Nondeterminism can therefore be viewed as involving “intuitive” insight
by which the best move can be chosen at every state (assuming that the NFA wants to accept every
string).

Example-1:- Consider the transition graph in Figure 2.6. It describes a nondeterministic accepter since
there are two transitions labeled a out of q0.

Figure-2.6

Example-2:- Given an NFA M = ({q0, q1, q2, q3}, {a, b}, , q0, {q3})and  given in transition table
indicated below, draw its transition diagram.

State (q) Input(x) Next state ( (q, x))

q0 a {q1, q2}
q1 b {q1, q3}
q2 λ {q3}
q2 a, b ∅
q3 a, b ∅
q1 a {q2}

Formal Languages and Automata Theory (SEng3042) Page 8

 DMIoT School of Computing Software Eng’g Ac/Program

Its transition graph is the following.

Example-3:-

A nondeterministic automaton is shown in the following figure. It is nondeterministic not only because
several edges with the same label originate from one vertex (i.e. q1, but also because it has a λ-
transition.

Some transitions, such as δ (q2, 0), are unspecified in the graph. This is to be interpreted as a transition
to the empty set, that is, δ (q2, 0) = Ø. The automaton accepts strings λ, 1010, and 101010, but not 110
and 10100. Note that for 10 there are two alternative walks, one leading to q0, the other to q2. Even
though q2 is not a final state, the string is accepted because one walk leads to a final state.

Again, the transition function can be extended so its second argument is a string. We require of the
extended transition function δ* that if then Qj is the set of all possible states the automaton may be in,
having started in state qi and having read w. A recursive definition of δ* is possible, but not particularly
enlightening. A more easily appreciated definition can be made through transition graphs.

δ* (qi, w) = Qj

For an NFA, the extended transition function is defined so that δ* (qi, w) contains qj if and only if there
is a walk in the transition graph from qi to qj labeled w. This holds for all qi, qj ∈ Q, and w ∈ Σ*.

Formal Languages and Automata Theory (SEng3042) Page 9

 DMIoT School of Computing Software Eng’g Ac/Program

Example:-

The following figure represents an NFA.

It has several λ-transitions and some undefined transitions such as δ(q2, a). Suppose we want to find δ*
(q1, a) and δ* (q2, λ). There is a walk labeled a involving two λ- transitions from q1 to itself. By using
some of the λ-edges twice, we see that there are also walks involving λ-transitions to q0 and q2.

Thus,
δ*(q1, a) = {q0, q1, q2}.

Since there is a λ-edge between q2 and q0, we have immediately that δ*(q2, λ) contains q0. Also, since
any state can be reached from itself by making no move, and consequently using no input symbol,
δ*(q2, λ) also contains q2. Therefore,
δ*(q2, λ) = {q0, q2}

Using as many λ-transitions as needed, you can also check that

δ*(q2, aa) = {q0, q1, q2}

As for DFA's, the language accepted by NFA is defined formally by the extended transition function.
The language L accepted by an NFA M = (Q, Σ, δ, q0, F) is defined as the set of all strings accepted in
the above sense. Formally,

L(M) = {w ∈ Σ*: (q0, w) ∩ F ≠ ∅}

In words, 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:-

What is the language accepted by the automaton in the above figure of Example-3?

Formal Languages and Automata Theory (SEng3042) Page 10

 DMIoT School of Computing Software Eng’g Ac/Program

It is easy to see from the graph that the only way the NFA can stop in a final state is if the input is
either a repetition of the string 10 or the empty string. Therefore, the automaton accepts the language
L= {(10)n : n ≥0}.

What happens when this automaton is presented with the string w = 110? After reading the prefix 11,
the automaton finds itself in state q2, with the transition δ(q2, 0) undefined. We call such a situation
a dead configuration, and we can visualize it as the automaton simply stopping without further
action. But we must always keep in mind that such visualizations are imprecise and carry with them
some danger of misinterpretation. Thus, no final state can be reached by processing w = 110, and
hence the string is not accepted.

δ*(q0, 110) = ∅

2.4. Equivalence of Deterministic and Nondeterministic Finite Accepters

We now come to a fundamental question. In what sense are DFA's and NFA's different? Obviously,
there is a difference in their definition, but this does not imply that there is any essential distinction
between them. To explore this question, we introduce the concept of equivalence between automata.

Two finite accepters, M1 and M2, are said to be equivalent if that is, if they both accept the same
language

L(M1) = L(M2),

As mentioned, there are generally many accepters for a given language, so any DFA or NFA has
many equivalent accepters.

The DFA shown in the following figure is equivalent to the NFA in showed in Example-3 since they
both accept the language {(10)n : n ≥0}.

When we compare different classes of automata, the question invariably arises whether one class
is more powerful than the other. By “more powerful” we mean that an automaton of one kind can
achieve something that cannot be done by any automaton of the other kind. Let us look at this question

Formal Languages and Automata Theory (SEng3042) Page 11

 DMIoT School of Computing Software Eng’g Ac/Program

for finite accepters. Since a DFA is in essence a restricted kind of NFA, it is clear that any language
that is accepted by a DFA is also accepted by some NFA. But the converse is not so obvious. We
have added nondeterminism, so it is at least conceivable that there is a language accepted by some
NFA for which, in principle, we cannot find a DFA. But it turns out that this is not so. The classes of
DFA's and NFA's are equally powerful: For every language accepted by some NFA there is a DFA
that accepts the same language.

This means that we can actually give a way of converting any NFA into an equivalent DFA. The
construction is not hard to understand; once the idea is clear it becomes the starting point for a
rigorous argument. The rationale for the construction is the following. After an NFA has read a string
w, we may not know exactly what state it will be in, but we can say that it must be in one state of a
set of possible states, say {qi, qj,…, qk}. An equivalent DFA after reading the same string must be in
some definite state. How can we make these two situations correspond? The answer is a nice trick:
Label the states of the DFA with a set of states in such a way that, after reading w, the equivalent
DFA will be in a single state labeled {qi, qj, …, qk}. Since for a set of |Q| states there are exactly 2|Q|
subsets, the corresponding DFA will have a finite number of states. Most of the work in this suggested
construction lies in the analysis of the NFA to get the correspondence between possible states and
inputs. Before getting to the formal description of this, let us illustrate it with a simple example.

Example:-

Convert the NFA in the following figure to an equivalent DFA.

The NFA starts in state q0, so the initial state of the DFA will be labeled {q0}. After reading an a, the
NFA can be in state q1 or, by making a λ-transition, in state q2. Therefore, the corresponding DFA
must have a state labeled {q1, q2} and a transition
δ({q0}, a) = {q1, q2}.

In state q0, the NFA has no specified transition when the input is b; therefore,
δ ({q0}, b) = Ø.

Formal Languages and Automata Theory (SEng3042) Page 12

 DMIoT School of Computing Software Eng’g Ac/Program

A state labeled Ø represents an impossible move for the NFA and, therefore, means non acceptance
of the string. Consequently, this state in the DFA must be a non-final trap state.

We have now introduced into the DFA the state {q1, q2}, so we need to find the transitions out of
this state. Remember that this state of the DFA corresponds to two possible states of the NFA, so we
must refer back to the NFA. If the NFA is in state q1 and reads an a, it can go to q1. Furthermore,
from q1 the NFA can make a λ-transition to q2. If, for the same input, the NFA is in state q2, then there
is no specified transition. Therefore,
δ({q1, q2}, a) = {q1, q2}.

Similarly,
δ({q1, q2}, b) = {q0}

At this point, every state has all transitions defined. The result, shown in the following figure, is a
DFA, equivalent to the NFA with which we started. The NFA in the previous figure accepts any
string for which δ* (q0, w) contains q1. For the corresponding DFA to accept every such w, any state
whose label includes q1 must be made a final state.

Theorem

Let L be the language accepted by a nondeterministic finite accepter MN = (QN, Σ, δN, q0, FN). Then
there exists a deterministic finite accepter MD = (QD, Σ, δD,{q0}, FD) such that L= L(MD).

Proof: Given MN, we use the procedure NFA-to-DFA below to construct the transition graph GD
for MD. To understand the construction, remember that GD has to have certain properties. Every
vertex must have exactly |Σ| outgoing edges, each labeled with a different element of Σ. During the

Formal Languages and Automata Theory (SEng3042) Page 13

 DMIoT School of Computing Software Eng’g Ac/Program

construction, some of the edges may be missing, but the procedure continues until they are all there.
Procedure: NFA-to-DFA
1. Create a graph GD with vertex {q0}. Identify this vertex as the initial vertex.
2. Repeat the following steps until no more edges are missing.
Take any vertex {qi, qj,…, qk} of GD that has no outgoing edge for some a ∈ Σ Compute
δ*N (qi, a), δ*N (qj, a), …, δ*N (qk, a)
If
δ*N (qi, a) ∪ δ*N (qj, a) ∪ … ∪ δ*N (qk, a) = {ql, qm,…, qn}
create a vertex for GD labeled {ql, qm,…, qn}if it does not already exist. Add to GD an edge from
{qi, qj,…, qk} and label it with a.
3. Every state of GD whose label contains any qf ∈ FN is identified as a final vertex.
4. If MN accepts λ, the vertex {q0} in GD is also made a final vertex.
It is clear that this procedure always terminates. Each pass through the loop in Step 2 adds an
edge to GD. But GD has at most 2|QN| |Σ| edges, so that the loop eventually stops.

Example-1:-
Convert the NFA shown below into an equivalent deterministic machine.

Since δ(q0, 0) = {q0, q1}, we introduce the state {q0, q1} in GD and add an edge labeled 0 between
{q0}and {q0,q1}. In the same way, considering δN (q0, 1) = {q1} gives us the new state {q1} and an
edge labeled 1 between it and {q0}. There are now a number of missing edges, so we continue, using
the construction of the previous theorem. Looking at the state {q0, qi}, we see that there is no
outgoing edge labeled 0, so we compute
δ*N (q0, 0) ∪ δ*N (q1, 0) = {q0, q1, q2}

This gives us the new state {q0, q1, q2} and the transition
δD ({q0, q1}, 0) = {q0, q1, q2}

Then, using a =1, i = 0, j = 1, k = 2,

δ*N (q0, 1) ∪ δ*N (q1, 1) ∪ δ*N (q2, 1) = {q1, q2}

Formal Languages and Automata Theory (SEng3042) Page 14

 DMIoT School of Computing Software Eng’g Ac/Program

makes it necessary to introduce yet another state { q1, q2}. At this point, we have the partially
constructed automaton shown in the following figure.

Since there are still some missing edges, we continue until we obtain the complete solution in the
following figure.

One important conclusion we can draw from the previous theorem is that every language accepted
by an NFA is regular.

 How to convert NFA with epsilon to DFA?

Before looking the conversion method for NFA involving epsilon to DFA, let us see what epsilon closure is.

The ε closure (P) is a set of states which are reachable from state P on ε-transitions.
The epsilon closure is as mentioned below −
 ε-closure (P) = P, where P ∈ Q
 If there exists ε-closure (P) = {q} and 𝛿(q, ε) =r then, ε-closure (P) = {q, r}

Formal Languages and Automata Theory (SEng3042) Page 15

 DMIoT School of Computing Software Eng’g Ac/Program

For example, for the NFA shown below

 ε-closure (q0) = {q0, q1, q2}; i.e. self-state + ε-reachable states.

 ε-closure (q1) = { q1, q2}; q1 is self-state and q2 is a state obtained from q1 with epsilon input.
 ε-closure (q2) = {q2}

Now let us back to the way for converting NFA with epsilon to DFA,
The method for converting the NFA with ε to DFA is explained below.
Step 1 − Consider M = {Q, Σ, δ, q0, F) is NFA with ε. We have to convert this NFA with ε to
equivalent DFA denoted by M0 = (Q0, Σ, δ0, q0, F0)

Then obtain,
ε-closure(q0) ={p1, p2, p3,……pn}
then [p1, p2, p3,….pn] becomes a start state of DFA
now[p1, p2, p3,….pn] ∈ Q0

Step 2 − We will obtain δ transition on [p1, p2, p3,…pn] for each input.
δ0([p1, p2, p3,..pn], a) = ε-closure(δ(p1, a) ∪ δ(p2, a) ∪ … ∪ δ(pn, a)) = ∪ (i = 1 to n) ε-closure δ(pi, a)
Where a is input ∈Σ.

Step 3 − The state obtained [p1, p2, p3,…pn] ∈ Q0 .

The states containing final state in pi is a final state in DFA
Example
Convert the following NFA with epsilon to equivalent DFA

Solution:-

Formal Languages and Automata Theory (SEng3042) Page 16

 DMIoT School of Computing Software Eng’g Ac/Program

To convert this NFA with epsilon, we will first find the ε-closures, as given below −
 ε-closure(q0) = {q0, q1, q2}

 ε-closure(q1) = {q1, q2}

 ε-closure(q2) = {q2}

Let us start from ε-closure of start state, as mentioned below −

When, ε-closure(q0) ={q0, q1, q2}, we will call this state as A.
Now, let us find transition on A with every input symbol, as shown below −
δ'(A, a) = ε-closure(δ(A, a))
= ε-closure(δ(q0, q1, q2), a))
= ε-closure(δ(q0, a) ∪ δ(q1, a) ∪ δ(q2, a) )
= ε-closure(∅ ∪ q1 ∪ q2)
= ε-closure(q1)
= {q1, q2} let us call it as state B
δ'(A, b) = ε-closure(δ(A,b))
= ε-closure(δ(q0,q1,q2), b))
= ε-closure(δ(q0, b) ∪ δ(q1,b) ∪ δ(q2,b) )
= ε-closure(q0 ∪ ∅ ∪ q0)
= ε-closure(q0)
= {q0, q1, q2} its nothing but state A
δ'(B, a) = ε-closure(δ(B, a))
= ε-closure(δ(q1, q2), a))
= ε-closure(δ(q1, a) ∪ δ(q2, a) )
= ε-closure(q1 ∪ q1)
= ε-closure(q1)
= {q1, q2} its nothing but state B
δ'(B, b) = ε-closure(δ(B, b))
= ε-closure(δ(q1, q2), b))
= ε-closure(δ(q1, b) ∪ δ(q2, b) )
= ε-closure(∅ ∪ q0)
= ε-closure(q0)
= {q0, q1, q2} its nothing but state A

Hence, the transition table for the generated DFA is as follows.

Formal Languages and Automata Theory (SEng3042) Page 17

 DMIoT School of Computing Software Eng’g Ac/Program

States\inputs a b
A B A
B B A
Note that:-
 As, A = {q0, q1, q2} in which the final state q2 lies. Hence, A is the final state.
 In B = {q1, q2} the state q2 lies. Hence, B is also the final state.

Exercise:- Draw the DFA transition diagram based on the above information!

NFA with ε can be converted to NFA without ε and this NFA without ε can be converted to DFA.
Here we are going to discuss these conversions and will find them equivalent to each other.

Conversion from NFA with ε to NFA without ε:

Step1: Find out all the ε transition from each state from Q. (Find ε – closure for each states from Q)
Step2: Find δ’ transition (means ε – closure on δ with ε moves)
Step3: Repeat step2 for each input symbol and for each state
Step4: From the resultant transition table can construct the NFA without ε

For example:- convert the given NFA with ε to

NFA without ε
Solution
Step1: Find ε – closure for each states

Step2: Find δ’ transition for each state on each input symbol.

Formal Languages and Automata Theory (SEng3042) Page 18

DMIoT School of Computing Software Eng’g Ac/Program

Formal Languages and Automata Theory (SEng3042) Page 19

 DMIoT School of Computing Software Eng’g Ac/Program

The transition table for the required NFA will be the following.

The NFA will be the following.

Exercise-2:- Convert the NFA indicated below to DFA and draw its transition diagram.

2.5. Reducing number of states in Finite Automata

Any DFA defines a unique language, but the converse is not true. For a given language, there are
many DFA's that accept it. There may be a considerable difference in the number of states of such
equivalent automata. In terms of the questions we have considered so far, all solutions are equally

Formal Languages and Automata Theory (SEng3042) Page 20

 DMIoT School of Computing Software Eng’g Ac/Program

satisfactory, but if the results are to be applied in a practical setting, there may be reasons for
preferring one over another.

The two DFA's depicted below figure (a) and (b) are equivalent, as a few test strings will quickly
reveal. We notice some obviously unnecessary features of figure (a). The state q5 plays
absolutely no role in the automaton since it can never be reached from the initial state q0. Such a
state is inaccessible, and it can be removed (along with all transitions relating to it) without affecting
the language accepted by the automaton. But even after the removal of q5, the first automaton has
some redundant parts. The states reachable subsequent to the first move δ (q0, 0) mirror those
reachable from a first move δ (q0, 1). The second automaton combines these two options.

From a strictly theoretical point of view, there is little reason for preferring the automaton in
Figure (b) over that in Figure (a). However, in terms of simplicity, the second alternative is
clearly preferable. Representation of an automaton for the purpose of computation requires space
proportional to the number of states. For storage efficiency, it is desirable to reduce the number of
states as far as possible.

We have to follow the various steps to minimize the DFA. These are as follows:
Step 1: Remove all the states that are unreachable from the initial state via any set of the transition of DFA.
Step 2: Draw the transition table for all pair of states.
Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states, and T2 contains
non-final states.

Formal Languages and Automata Theory (SEng3042) Page 21

 DMIoT School of Computing Software Eng’g Ac/Program

Step 4: Find similar rows from T1 such that:

1. δ (q, a) = p
2. δ (r, a) = p
That means, find the two states which have the same value of a and b and remove one of them.
Step 5: Repeat step 3 until we find no similar rows available in the transition table T1.
Step 6: Repeat step 3 and step 4 for table T2 also.
Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the transition
table of minimized DFA.
For Example: minimize the following DFA

Solution:
Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them.
Step 2: Draw the transition table for the rest of the states.
State 0 1
→q0 q1 q3
q1 q0 q3
*q3 q5 q5
*q5 q5 q5

Step 3: Now divide rows of transition table into two sets as:
i. One set contains those rows, which start from non-final states:
State 0 1
q0 q1 q3
q1 q0 q3

Formal Languages and Automata Theory (SEng3042) Page 22

 DMIoT School of Computing Software Eng’g Ac/Program

ii. Another set contains those rows, which starts from final states.
State 0 1
q3 q5 q5
q5 q5 q5

Step 4: Set 1 has no similar rows so set 1 will be the same.

Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to the same state on 0 and 1.
So skip q5 and then replace q5 by q3 in the rest.
State 0 1

q3 q3 q3

Step 6: Now combine set 1 and set 2 as:

State 0 1
→q0 q1 q3
q1 q0 q3
*q3 q3 q3

Now it is the transition table of minimized DFA. The minimized DFA is shown in the following
figure.

Formal Languages and Automata Theory (SEng3042) Page 23