2
Finite Automata
In this chapter, we introduce the definition of Finite Automaton (FA) and also some realtime problems that can be solved using FA. Representation of FA is done using 5tuple form, transition table and transition diagram. Definitions of nondeterministic and deterministic FAs are explained with examples and, further, how these automata act as language acceptor is elaborated. Equivalence of NFAswithɛ to NFAswithoutɛ, and equivalence of NFAs to DFAs are explained. Minimizing the given automaton using Myhill Nerode and π construction method, and testing the equivalence of two FAs are discussed. Moore and Mealy machines, which represent Finite Automaton with output, are explained with examples.
2.1 Finitestate Machine
The finitestate system represents a mathematical model of a system with some input. The model finally gives some output. The input supplied to the machine is processed by various states. These states are called intermediate states.
Good example of finitestate systems is a control mechanism of elevator. This mechanism remembers only the current floor number pressed; it does not remember any of the previously pressed numbers.
Another good example is a bulb operated with a single switch. Switch has two possibilities: it closes or opens the circuit. When the circuit is closed the current passes and the bulb glows.
From the above statement it is clear that the bulb will be either in ON state or OFF state. If it is in ON state and if the current passes through it, then the bulb will glow. If no current is passed then it changes to OFF state. The flow of current is indicated by value 1, and blocked state of current flow is indicated by 0. The functioning of the bulb can be shown in the form of a table:
State 
Current = 1 
Current = 0 

ON 
ON 
OFF 
OFF 
ON 
OFF 
This is a finite system that represents the functioning of a bulb. Many realtime problems can be represented using such mathematical models.
The finitestate systems are useful in designing text editors, lexical analysers and natural language processing.
Definition 1: A finite automaton is formerly defined as a 5tuple (Q, ∑, δ, q_{0}, F) where
Q  is a finite set of states which is nonempty 
∑  is the input alphabet 
q_{0}  is the initial state 
F  is a set of final states and F ⊆ Q 
δ  is a transition function or mapping function Qx ∑ → Q using this the next state can be determined depending on the current input. 
2.1.1 FiniteAutomaton Model
The finite automaton can be represented as input tape and finite control as shown in the Figure 2.1:
 Input tape: is a linear tape having some cells that can hold an input symbol from ∑.
 Finite control: The finite control indicates the current state and it decides on the next state on receiving particular input from input tape. The tape reader reads the cells one by one from left to right, and at any instance only one input symbol is read.
Fig 2.1 Finite Automaton
The reading head examines the read symbol, and the head moves to the right with or without changing the state. When the entire string is read, if finite control is in final state, the string is accepted; else it is rejected. Finite automaton can be represented by the transition diagram, in which the vertices represent the states and edges represent transitions. We can model the realword problems as a finite automaton and this helps in understanding the behaviour and in analysing the behaviour.
Fig 2.2 Combinational Circuit
Consider the following combinational circuit shown in Figure 2.2 represent the circuit using finite state system.
A circle with * (or ) represents AND gate, represents OR gate and represents inverter or NOT gate. By changing the signals at U_{1}, U_{2} and i/p signal x we get output Z_{1}* Z_{2}. This behaviour can be shown as an FA:
If output expected is 1, then states [11] become an accepting state of the finite automaton. Figure 2.3 gives a simple model of a combinational circuit, which helps us in analysing the behaviour, by changing signal at Z_{1}Z_{2}.
U_{1} U_{2} 
0 
1 
z_{1} z_{2} 
z_{1} z_{2} 

0 
0 
1 
1 
11 
1 
11 
11 
10 
10 
0 
10 
Fig 2.3 Finite Automaton For Combinational Circuit
Lexical analyser behaviour can be shown as an FA. Consider the lexical analyser that matches words such as ‘the’, ‘this’, ‘that’, ‘to’ shown as FA in Figure 2.4.
Fig 2.4 Simple Lexical Analyzer
These systems are called finite automaton as the number of possible states and the number of letters in the alphabet are, both, finite. It is automaton because the change of state is totally governed by the input.
2.1.2 Properties of Transition Function ‘x’
The transition function δ defined as Q × ∑→ Q holds the following properties for all states q ∈ Q and a ∈ ∑^{*}
 δ (q, ε) = q. The states of the FA are changed only by an input symbol.
 For all strings w and i/p symbol a,δ (q, aw) = δ (δ (q, a), w)
An FA can be represented by a
 Transition diagram
 Transition table
2.1.3 Transition Diagram
A transition graph contains
 Set of states as circles
Start state q_{0 }with arrow
Final state by double circle (Figure 2.5).
Fig. 2.5 Representation of Final States
 A finite set of transitions (edgeslabels) that shows how to go from one state to another state as shown in Figure 2.6.
2.1.4 Transition Table
Following is a tabular representation where rows correspond to states and columns correspond to input. Start state is given by → and the final state by *
M = {{q_{0}, q_{1}, q_{2}}, {a, b}, δ, q_{0}, {q_{2}}}
δ (q_{0}, a) = q_{1} 
δ (q_{0}, b) = q_{2} 
δ (q_{1}, a) = q_{2} 
δ (q_{1}, b) = q_{0} 
δ (q_{2}, a) = q_{2} 
δ (q_{2}, b) = q_{2}_{ } 
Δ/Σ 
a 
b 
→ q_{0} 
q_{1} 
q_{2} 
q_{1} 
q_{2} 
q_{0} 
*q_{2} 
q_{2} 
q_{2} 
The same table can be shown as a transition diagram (Figure 2.6)
Fig 2.6 Transition Diagram
2.2 Language Acceptance
A string w is accepted by finite automaton U = {Q, ∑, δ, q_{0}, F} if δ (q_{0},_{ }w) = P for some P in F. This concludes that string is accepted when it enters into the final state on inputting the last element.
Let us check if the input string 1010 is accepted or not: by FA shown in Figure 2.7.
Here q_{0 }is the final state. Hence, the string is accepted.
b) Check 11111
q_{2 }∉ F. Hence, this string is rejected.
Fig 2.7 Finite Automaton
Give the language defined by the following FA: shown in Figure 2.8.
If we list the different strings accepted by this automata, we get
We observe that all the strings accepted are ending with 1.
Language accepted by machine M (denoted by L(M)) is given by the set of strings that are ending with 1.
Fig 2.8 FA for Example 2.5
Identify the language defined by following machine: in Figure 2.9.
In this automaton, since the initial state and the final state are same, it accepts ε and all strings that end with 0. Hence the language accepted by this L(M) = {w/w is ε or all strings that end with 0}
or
L(M) = {w/w is ε or all strings that do not end with 1}
Fig 2.9 FA for Example 2.6
Identify the language defined by following machine:in Figure 2.10.
Fig 2.10 FA for Example 2.7
The strings valid in the language are
L(m) = {w/w contains all strings that start and end with same symbol}
2.3 Two Types of Finite Automata
 Deterministic finite automata (DFA)
 Nondeterministic finite automata (NFA)
In DFA, there will be a unique transition in any state on an input symbol. In NFA, there can be more than one transition on an input symbol. Hence, DFA is faster than NFA. The Figure 2.10 is an example of a DFA. The Figure 2.11 is an example of NFA.
In Figure 2.11 in state q_{0} on 0, it is either in state q_{0} or in state q_{1}. Hence it is a NFA.
Fig 2.11 Non Deterministic Finite Automaton
2.3.1 Deterministic Finite Automata (DFA)
Definition 2: Deterministic finite automata can be defined as quintuple
where 
M = (Q, ∑, δ, q_{0}, F) Q = a nonempty finite set, of states ∑ = input alphabet q_{0} = initial start state F = set of final states δ = transition function that takes two arguments, a state and an input symbol, and returns output as state, that is, δ: Q × ∑ → Q 
Example: δ (q_{1}, a) = q_{1}
DFA can be used as finite acceptor because its sole job is to accept certain input strings and reject others.
It is also called language recognizer because it merely recognizes whether the input strings are in the language or not.
Design a DFA which accepts only input 101 over the set {0, 1}
Fig 2.12 FA with Trap State
Solution: Here q_{trap} is called trap state/dummy state where unnecessary transitions are thrown away (Figure 2.12).
Design a DFA that accepts even number of 0’s and even number of 1’s.
Solution: This FA will have four different possibilities:
Even number of 0’s and even number of 1’s – q_{0}
Odd number of 0’s and even number of 1’s – q_{1}
Even number of 0’s and odd number of 1’s – q_{2}
Odd number of 0’s and odd number of 1’s – q_{3 }
where states are q_{0}, q_{1}, q_{2 }and q_{3}. Since the state q_{0 }indicates the condition of even number of 0’s and even number of 1’s, this state is made the final state. The DFA is given by Figure 2.13.
Fig 2.13 DFA for Example 2.9
Design a DFA that accepts all the strings with at most 3 a’s.
Solution: Strings that have more than three a’s should not be accepted. There are five possibilities. Hence, the DFA requires five states:
No a’s 
– q_{0} (Accepting state) 
One a 
– q_{1} (Accepting state) 
Two a’s 
– q_{2} (Accepting state) 
Three a’s 
– q_{3} (Accepting state) 
Four a’s 
– q_{4} (for dummy state indicating a nonaccepting state) 
Deterministic finite automata can be constructed by expanding the listed conditions as shown in Figure 2.14.
Fig 2.14 DFA for Example 2.10
Draw a DFA that recognizes the set of all strings starting with prefix ab with alphabets from ∑ = {a. b}.
Solution: This automaton should accept strings that start with ab (and then followed by arbitrary elements). It should reject strings that start with b. Hence, if it sees b at the initial state, it should enter the dead state, from which there is no path to the final state. After a, it should find b. Hence, in the second state if it sees a, it should enter the dead state. Once it sees ab, it is the final state and remains in the same state on any element. Figure 2.15 shows the resultant DFA.
Fig 2.15 DFA for Example 2.11
Design a DFA that accepts even number of a’s over ∑ = {a}.
Solution: This automaton should accept strings that have even number of a’s. On seeing a’s which form an even count, the DFA should be in final state and on seeing odd count of a’s, it should be in nonfinal state as shown in Figure 2.16.
Fig 2.16 DFA for Example 2.12
Fig 2.17 DFA for Example 2.12 With More States
This DFA is not unique. The same machine can also be designed as in Figure 2.17.
Both DFAs represent the same language but with different number of states. It is always better to have less number of states as it simplifies the implementation.
DFA that accepts odd number of 1’s on {0, 1}.
Solution: This automaton should accept strings that have odd number of 1’s and any number of 0’s. On seeing 1’s that form an odd count, the DFA should be in the final state and, on seeing even count of 1’s, it should be in nonfinal state as shown in Figure 2.18.
Fig 2.18 DFA for Example 2.13
Design a DFA that contains 001 as substring in all strings over ∑ = {0, 1}.
This automaton should accept strings that have substring ‘001’. On seeing ‘0’ go to next q_{1} state, otherwise be in same state. In q_{1} state, on seeing ‘0’, go to next q_{2} state; otherwise go to the initial state, as the substring would not be ‘00’. In q_{2} state, on seeing ‘1’, go to next q_{3} state, otherwise be in same state, as it would satisfy the required condition that 1 should be preceded by ‘00’. Declare q_{3} as final state, as the required total condition is satisfied and is shown in Figure 2.19.
Fig 2.19 DFA for Example 2.14
2.3.2 Nondeterministic Finite Automaton (NFA)
In this automaton, for a given input symbol, there can be more than one transition from a state. Such automaton is called Nondeterministic Finite Automaton. NFA is mathematically described as a quintuple.
Definition 3: Nondeterministic finite automata can be defined as quintuple
where 
M = (Q, ∑, δ, q_{0}, F) Q = Nonempty finite set of states ∑ = input alphabet which includes q_{0} = initial start state F = set of final states δ = transition function that takes two arguments (a state and an input symbol) and returns an output as state, that is, δ: Q X ∑ →2^{Q} 
2.3.3 Acceptance of NFA
Acceptance of a string is defined as ‘reaching final states on processing the input string’ i.e. if there exits atleast one path from start state to final state, then the string is accepted by NFA.
Check if 0100 is accepted or not. by automata in Figure 2.20.
Fig 2.20 Simple NFA
As there is a path from q_{0 }to final state q_{n }the string is accepted. Thus we check all possible paths from start state.
Note: It is easy to construct a NFA than a DFA. But for a given string, the processing time of NFA is greater than that of a DFA.
Design NFA for {abab^{n}/n > = 0}
Solution: Read the sequence a, b, a in state q_{0} and q_{1}, q_{2} and q_{3} in sequence. Since b^{n}, n ≥ 0 indicates zero or more no of b’s in state q_{3} add self loop in this state and declare it as final state and is shown in Figure 2.21.
Fig 2.21 NFA for Example 2.15
Design NFA for the set of strings such that 5^{th} symbol from right end is 1.
Solution: Since fifth symbol from right end is 1, we can have minimum 6 states.
The first transition should be on 1, remaining can be either 0 or 1 and is shown in Figure 2.22.
Fig 2.22 NFA for Example 2.16
Design a NFA and DFA accepting all the strings ending with 01 over ∑ = {0, 1}
Solution: We can have any string on 0 or 1 but it should end with 0 followed by 1. The corresponding NFA is shown in Figure 2.23.
Fig 2.23 NFA for Example 2.17
Corresponding DFA is shown in Figure 2.24.
Fig 2.24 DFA for Example 2.17
So drawing NFA is simpler than drawing DFA.
2.4 Equivalence of DFAs and NFAs
Theorem 1: Let L be a set accepted by a NFA. Then there exists a DFA that accepts L.
Proof: Let M = (Q, ∑, δ, q_{0}, F) be a NFA accepting L.
Define DFA M^{1} = (Q^{1}, ∑^{ 1}, δ^{1}, q_{0}^{1}, F^{1}) as follows.
The states of M^{1} are all the subsets of the set of states of M, that is, Q^{1} = 2^{Q}.
If Q = {A, B} then Q^{1} = {φ, [A], [B], [AB]}. F^{1} is the set of all states in Q^{1} containing a final state of M. If F = {B} then F^{1} = {[B], [AB]}.
An element of Q^{1} will be denoted by [q_{1},_{ }q_{2},……q_{i}] where q_{1},_{ }q_{2},……q_{i }are in Q.
Note: [q_{1}, q_{2},…q_{i}]^{ }is a single state of DFA corresponding to the set of states of NFA.
We define δ^{1} ([q_{1},_{ }q_{2},…q_{i}], a) = [P_{1}, P_{2},…..P_{i}]
that is, δ^{1} applied to an element [q_{1},_{ }q_{2},…q_{i}] of Q^{1} is computed by applying δ to each state of Q represented by [q_{1},_{ }q_{2},…q_{i}]. It is easy to show by induction on length of the input string x that
Basis: The result is trivial for x = 0. As δ (q_{0}^{1}, ε) = [q_{0}] ⇒ q_{0}^{1} = [q_{0}]
Induction: Suppose that the hypothesis is true for inputs of length m or less. Let ‘xa’ be a string of length m + 1 with a in ∑. Then
But by the definition of δ^{1}
Thus
This establishes the inductive hypothesis.
Now we have to prove that the L(M) = L(M^{1}).
The string x is accepted by NFA or DFA only if it is in one of the final states.
For a string x in NFA, let δ (q_{0}, x) = P where P ∈ F. Then δ^{1}(q_{0},_{ }x) = [P] where [P] ∈ F^{1}, Hence,the string x is accepted if it is accepted by NFA.
Note
 Every language that can be described by NFA can be described by some DFA
 DFA in practice has more states than NFA
 DFA equivalent to NFA can have at most 2^{n} states whereas NFA has only n states.
2.5 Converting NFA (M_{N}) to DFA (M_{D})— Subset Construction
Let M_{N} = (Q_{N}, ∑_{N}, δ_{n}, q_{ON}, F_{N}) be the given NFA to construct equivalent DFA M_{D}. Define
M_{D} as follows.
 Q_{D} = 2^{Q}N. If NFA has n states, DFA can have at most 2^{n} states.
 ∑_{n} = ∑_{D}
 [q_{0}] = {q_{n}}
 F_{D} = Set of all states of Q_{D} that contains at least one of the final states of F_{N}.
 δ_{D}((q_{1}, q_{2}, q_{3}), a) = δ_{n}(q_{1}, a) ∪ δ_{n} (q_{2}, a) ∪ δ_{n}(q_{3}, a)
= {P_{1}, P_{2}, P_{3}} say
Add the state [P_{1}, P_{2}, P_{3}] to Q_{D} if it is not there.
Convert the NFA shown in the Figure 2.25 to DFA.
Fig 2.25 NFA
Solution:
Step 1: Find the possible set of states Q.
Then Q has 2^{2} (= 4) states, and it is the set of all subsets of q_{0}, q_{1}:
{Ø, [q_{0}], [q_{1}], [q_{0}q_{1}]}
Step 2: Find the initial state.
[q_{0 }] = q_{0}
Step 3: Define the transitions on 0, 1, on each state.
δ(q_{0}, 0) = [q_{0}, q_{1}]
δ(q_{0}, 1) = [q_{1}]
δ(q_{1}, 0) = [q_{1}]
δ(q_{1}, 1) = [q_{0}, q_{1}]
δ([q_{0}, q_{1}], 0) = δ(q_{0}, 0) ∪ δ(q_{1}, 0) = [q_{0}, q_{1}]
δ([q_{0}, q_{1}], 1) = δ(q_{0}, 1) ∪ δ(q_{1}, 1) = [q_{0}, q_{1}]
F = The set of states that contain q_{0}, called the final states in DFA. [q_{0}], [q_{0}, q_{1}]
Step 4: Transition diagram of the DFA is shown in Figure 2.26. In the set of states, we have not used the state Ø as it is not reached.
Fig 2.26 Equivalent DFA
Convert the NFA in Figure 2.27 to DFA.
Solution:
Q has 2^{3} (= 8) states, and it is the set of all subsets of q_{0}, q_{1}, q_{2}:
{Ø, [q_{0}], [q_{1}], [q_{2}], [q_{0}, q_{1}], [q_{0}, q_{2}], [q_{1}, q_{2}], [q_{0}, q_{1}, q_{2}]}
∑ = 0, 1
q_{0 }= [q_{0}]
F = {[q_{2}], [q_{0}, q_{2}], [q_{1}, q_{2}], [q_{0}, q_{1}, q_{2}]}_{ }
δ is given by δ_{D}([q_{1} q_{2}], a) = δ_{n }(q_{1},_{ }a) U δ_{n }(q_{2},_{ }a)
where δ_{n} is transition function of NFA
Fig 2.27 NFA
0 
1 

Ø 
Ø 
Ø 
→[q_{0}] 
[q_{0}, q_{1}] 
[q_{0}] 
[q_{1}] 
Ø 
[q_{2}] 
[q_{2}] 
Ø 
Ø 
[q_{0}, q_{1}] 
[q_{0}, q_{1}] 
[q_{0}, q_{2}] 
*[q_{0}, q_{2}] 
[q_{0}, q_{1}] 
[q_{0}] 
[q_{1}, q_{2}] 
Ø 
[q_{2}] 
[q_{0}, q_{1}, q_{2}] 
[q_{0}, q_{1}] 
[q_{0}, q_{2}] 
The states φ, [q_{1}], [q_{2}], [q_{1}, q_{2}] and [q_{0}, q_{1}, q_{2}] are not reachable from start state. Hence, they cannot define any string. So they can be thrown away. Hence the DFA can be simplified as in Figure 2.28.
Fig 2.28 Equivalent DFA for Example 2.19
To get this simplified DFA, construct the states of DFA as follows:
 Start with the initial state. Do not add all subsets of states as there may be unnecessary states.
 After finding the transition on this initial state, include only the resultant states into the list until no new state is added to the list. For example, if δ(q_{0}, a) = {q_{0}, q_{1}} (say), then add this as a new state in DFA and find the transition from this state on the input symbol.
 Declare the states as final if they have at least one final state of the NFA.
Convert the following NFA to a DFA.
δ 
0 
1 
→q_{0} 
{q_{1} q_{2}} 
{q_{0}} 
q_{1} 
{q_{0} q_{1}} 
Ø 
*q_{2} 
{q_{1}} 
{q_{0} q_{1}} 
Solution: DFA is
Q has 2^{3} (= 8) states, and it is the set of all subsets of q_{0}, q_{1}, q_{2}:
{Ø, [q_{0}], [q_{1}], [q_{2}], [q_{0}, q_{1}], [q_{0}, q_{2}], [q_{1}, q_{2}], [q_{0}, q_{1}, q_{2}]}
q_{0 }= [q_{0}]
F = {[q_{2}], [q_{0}, q_{2}], [q_{1}, q_{2}], [q_{0}, q_{1}, q_{2}]}
δ 
0 
1 
→[q_{0}] 
[q_{1} q_{2}] 
[q_{0}] 
*[q_{1} q_{2}] 
[q_{0} q_{1}] 
[q_{0} q_{1}] 
q_{0} q_{1}] 
[q_{0} q_{1} q_{2}] 
[q_{0}] 
*[q_{0} q_{1} q_{2}] 
[q_{0} q_{1} q_{2}] 
[q_{0} q_{1}] 
The transition diagram of DFA is as shown in Figure 2.29.
Fig 2.29 DFA for Example 2.20
2.6 NFA with Epsilon (ɛ) Transitions
We can extend a NFA by introducing ‘ɛmoves’ that allow us to make a transition on the empty string. There would be an edge labelled ɛ between two states and this edge allows transition from one state to another even without receiving an input symbol. This is another mechanism that allows NFA to be in multiple states at once. Constructing such NFA is easy, but the NFA thus constructed is not that powerful. The NFA with ɛmoves is given by M = (Q, ∑, δ, q_{0}, F) where δ is defined as Q X ∑ ∪ {ɛ} → 2^{Q}.
Figure 2.30 gives NFA with ɛ transitions and it accepts strings of the form {0^{n}1^{m}2^{o}/n, m, o ≥ 0}, that is, any number of 0’s followed by any number of 1’s followed by any number of 2’s.
Fig 2.30 NFA with ɛTransitions
Design NFA for language L = {0^{K}  k is multiple of 2 or 3}.
NFA for set of strings that have the characteristic that the number of 0’s in them is a multiple of 2 is given in Figure 2.31.
NFA for set of strings that have the characteristic that the number of 0’s in them is a multiple of 3 is given in Figure 2.32.
Fig 2.31 NFA for 0^{2k }
Fig 2.32 NFA for 0^{3k }
Combining these two NFAs, we get Figure 2.33.
Fig 2.33 NFA for 0^{2k }/0^{3k}
2.6.1 Epsilon Closure (ɛclosure)
Epsilon closure of a state is simply the set of all states that we can reach by ɛ input. This is denoted by either (q) or ɛclosure (q). In Figure 2.30: the epsilon closure of q_{0}, q_{1}, q_{2 }states are
ɛclosure (q_{0}) = {q_{0}, q_{1}, q_{2}}
ɛclosure (q_{1}) = {q_{1}, q_{2}}
ɛclosure (q_{2}) = {q_{2}}
Let us define the extended transition function for a NFA with ɛ transitions. For a regular NFA, for the induction step we defined
Then, we defined (q, wa) = S_{1} ∪ S_{2 }∪... ∪ S_{k}.
For a NFA with ɛ, we change for the definition of (q, wa) as follows:
This new definition includes the original sets S_{1}, S_{2}..., S_{k} as well as the states we can reach via ɛ transitions from these states.
2.6.2 Eliminating ɛTransitions
ɛTransitions are used for convenience in some cases, but they do not increase the power of the NFA. To eliminate them, we can convert a NFA with ɛ into an equivalent NFA without ɛ, by eliminating the ɛ edges and replacing them with the edges labelled with symbols present in Σ. We can also convert NFA with ɛ into an equivalent DFA, by steps quite similar to those we took for converting a normal NFA to a DFA, except that we must now follow all ɛtransitions and add those to our set of states.
2.6.3 Converting NFA with ɛTransition to NFA without ɛTransition
For each state compute ɛclosure(q) on each input symbol a ∈ Σ. If the ɛclosure of a state contains a final state then make the state final.
Let us consider the NFA with ɛtransitions depicted in Figure 2.34.
Fig 2.34 NFA with t
The transition table is
Step 1: Find ɛclosure of each state.
Step 2: Find the transition on each state for each element.
NFA without ɛtransitions is
Transition diagram of this NFA without ɛtransitions is given in Figure 2.35.
Fig. 2.35 NFA without ε
2.6.4 Converting NFA withɛtransition to DFA
 Compute ɛ^{*} for the current state, and this results in a set of states S.
 δ(S, a) is computed for all a ∈ Σ by the following steps:
 Let S = {p_{1}, p_{2}, ... p_{k}}
 Compute R = δ(S, a) by
This set is achieved by following input a, not by following any ɛtransition.
 Add the ɛtransitions by computing ɛclosure(R).
 Make a state an accepting state if it includes any final state in the NFA.
Note: The ɛ (epsilon)transition refers to a transition from one state to another without reading any input symbol (i.e. without the tape containing the input string moving). Epsilon transitions can be inserted between any two states.
Consider the NFA ɛ move machine M = {Q, Σ, δ, q_{0}, F}.
Q = {q_{0}, q_{1}, q_{2}}
Σ = {a, b, c} and ɛ moves
DFA construction
Step 1: Q has 2^{3} (= 8) states, and it is the set of all subsets of all subsets of q_{0}, q_{1}, q_{2}:
Step 2: Compute ɛclosure of each state.
Step 3: Find the initial state by finding the ɛclosure of the initial state.
Step 4: Explore the states that are valid states in DFA starting at the new initial state. Explore each new state by finding the transitions on every input element:
The next new state is [q_{1}, q_{2}] and the transitions for the new states are
The third new state is [q_{2}].
The last new state is [Ø] which is a dummy state, and the transitions are
Note: (Ø) = {Ø}
DFA transition table
Fig 2.36 DFA
2.7 Comparison Method for Testing Equivalence of Two FAs
Let M and M^{1} be two FAs over ∑. We construct a comparison table consisting of n + 1 columns where n is the number of input symbols.
 1^{st} column consists of pair of nodes of the form (q, q^{1}) where q ∈ M and q^{1 }∈ M^{1}.
 If (q, q^{1}) appears in some row of 1^{st} column, then the corresponding entry in the column of a (a ∈ ∑) is (q_{a}, q_{a}^{1}) where (q_{a}, q_{a}^{1}) are reachable from q and q^{1 }on a.
 Table is constructed by starting with a pair of initial vertices q_{in }and q_{in}^{1} of M and M^{1}. We complete the construction by considering the pairs that are not in 1^{st} column but are in the 2^{nd} and subsequent columns.
 If we reach a pair (q, q^{1}) such that q is in the set of final states of M and q^{1} is nonfinal state of M^{1} then terminate the construction and conclude that M and M^{1 }are not equivalent.
 If the construction is terminated when no new element that are not the 1^{st} column appears in the 2^{nd} and subsequent columns, conclude that M and M^{1 }are equivalent. To show the equivalence, let us consider the two DFA’s as shown in the Figures 2.37 and 2.38. Start at the initial state [q_{0}, q_{4}].
Fig 2.37 Finite Automata for Comparision
By looking at the number of states, we cannot conclude whether they are equivalent or not.
c 
d 

[q_{0}, q_{4}] 
[q_{3}, Ø] 
[q_{3}, q_{5}] 
Since we do not have a pair (q_{M1}q_{M2}) for input c, M_{1} and M_{2}^{ }are not equivalent.
2.8 Reduction of Number of States in FA
 Any DFA defines a unique language, but the converse of this is not true, that is, given a language, we cannot claim that there is a unique DFA associated.
 For one language, there can be many DFAs. So the number of states can consierably differ. By using comparison method we test this.
2.8.1 Indistinguishable States
Two states p and q of a DFA are indistinguishable if
and
Or for some string w ∈ ∑^{* }if δ^{*}(p, w) ∈ F and
δ^{*}(q, w) ∉ F (or vice versa), states p and q are said to be distinguishable by a string w.
2.8.2 Equivalent Classes
The concept of equivalent class is used in minimizing the number of states. States that are equivalent can be combined together into one class called equivalent class. Let us see the definition of equivalent states.
Definition 4: Two states q_{1} and_{ }q_{2} are equivalent (denoted by q_{1} ≡ q_{2}) if both δ(q_{1}, a) and δ(q_{2}, a) are final states or both of them are nonfinal states for all a ∈ ∑. These states are said to be 0equivalent.
Definition 5: Two states q_{1} and_{ }q_{2} are Kequivalent (denoted K ≥ O) if both δ(q_{1}, x) and δ(q_{2},_{ }x) are final states, or both are nonfinal states for all string x’s of length K or less.
Therefore, any two final states are K − equivalent if they belong to the same set in K − 1 step, otherwise they are not Kequivalent.
Properties:
P_{1}: The relation between q_{1} and q_{2} is an equivalent relation^{ }(i.e. Kequivalence relation) i.e it is reflexive, symmetric and transitive.
P_{2}: Every equivalence relation partitions set is also Kequivalence relation^{ }partition set Q.
P_{3}: If q_{1} and q_{2} are Kequivalent for all K ≥ 0, then they are equivalent.
P_{4}: If q_{1} and q_{2} are (K + 1)equivalent then they are Kequivalent.
2.8.3 Minimization of DFA
For any deterministic automaton, that has more number of states, we can construct its equivalent DFA with a less number of states. we can minimize the states of DFA as follows.
Construction of Minimum Automaton
 Initially construct 0equivalence class by ∏_{0} = {Q_{1}^{0}, Q_{2}^{0}} where Q_{1}^{0} is the set of final states and Q_{2}^{0} = Q − Q_{1}^{0 }is the set of nonfinal states.
 Construct ∏_{K}_{+}_{1 }from ∏_{K} by partitioning further:
 Let Q_{1}^{K }be any subset in ∏_{K}. If q_{1} and q_{2} are in Q_{1}^{K} they are (K + 1)equivalent provided δ(q_{1}, a) and δ(q_{2}, a) are Kequivalent.
 Find out whether δ(q_{1}, a) and δ(q_{2}, a) are in the same equivalence class in ∏_{K} for every a ∈ ∑. If so, q_{1 }and_{ }q_{2 }are_{ }(k + 1)equivalent. This way Q_{i }^{k} is further divided into (K + 1)equivalence classes. Repeat this for every Q_{i }^{k} in ∏_{K }to get all the elements of ∏_{K }_{+}_{ 1}.
 Construct ∏_{n }for n = 1, 2, 3, … until ∏_{n }= ∏_{n }_{+}_{ 1}.
 Construct the minimum state DFA with the states obtained by equivalent classes π_{n}.
First approach:
Find minimum finitestate automata for the DFA shown in Figure 2.38.
0 
1 

→a 
b 
f 
b 
g 
c 
*c 
a 
c 
e 
h 
f 
f 
c 
g 
g 
g 
e 
h 
g 
c 
Fig 2.38 DFA
Any two final states are 0equivalent, and any two nonfinal states are also 0equivalent.
From the above table, we find a, e, g are 1equivalent, b, h are 1 equivalent and d, f are 1equivalent. Hence,
∏_{1} (1, 3, 4, 5) = {{c}, {a, e, g}, {b, h}, {d, f}}
Using the new classes, we find whether they are 2equivalent.
∏_{2} (1, 6, 7, 8, 9) = {{c},{a, e}, {b, h}, {d, f}, {g}}
∏_{3} (1, 6, 7, 8, 9) = {{c},{a, e}, {b, h}, {d, f}, {g}}
From the above two relations, ∏_{2} and ∏_{3} are same. Hence, the final set of states are the sets 1, 6, 7, 8, 9 where {a, e}, {b, h}, {d, f}, {g}, {c} are all 3equivalent. The minimized DFA is depicted in Figure 2.39.
0 
1 

→{a, e} 
{b, h} 
{d, f} 
{b, h} 
{g} 
{c} 
*{c} 
{a, e} 
{c} 
{d,f} 
{c} 
{g} 
{g} 
{g} 
{a, e} 
Fig 2.39 Minimum State DFA
Second approach:
Construct the minimum DFA for the given DFA shown in Figure 2.40.
Fig 2.40 DFA
Solution: Let us represent the DFA as a transition table.
a = 0 
a = 1 

→q_{0} 
q_{1} 
q_{2} 
q_{1} 
q_{2} 
q_{4} 
q_{2} 
q_{3} 
q_{2} 
q_{3} 
q_{2} 
q_{4} 
*q_{4} 
q_{1} 
q_{4} 
 Initially we identify 0equivalence: ∏_{0} = {Q_{1}^{0}, Q_{2}^{0}} where Q_{1}^{0} is the set of final states and Q_{2}^{0} = Q − Q_{1}^{0 }is set of nonfinal states.
Q_{1}^{0} = {q_{4}}
Q_{2}^{0} = {q_{0}, q_{1}, q_{2}, q_{3}}
 Construct ∏_{1 }from ∏_{0} identifying the equivalent states in {Q_{1}^{0}, Q_{2}^{0}}.
Q_{1}^{0} cannot be divided as it has only one state.
Q_{2}^{0} has four states. We need to identify whether they are 1equivalent.
Compare q_{0}, q_{1} on input 0 and 1
δ(q_{0}, 0) = q_{1}δ(q_{1}, 0) = q_{2}Both of these resultant states belong to Q_{2}^{0}.
δ(q_{0}, 1) = q_{2}δ(q_{1}, 1) = q_{4}These resultant states belong to different sets in ∏_{0}
⇒ q_{0} is not 1equivalent to q_{1}
Compare q_{0}, q_{2} on input 0 and 1
both resultant states belong to Q_{2}^{0}.both resultant states belong to Q_{2}^{0}.⇒ q_{0} is 1equivalent to q_{2}Compare q_{0}, q_{3} on input 0 and 1
both resultant states belong to Q_{2}^{0}.both resultant states belong to different sets in ∏_{o}.q_{0} is not 1equivalent to q_{3 }Therefore,
∏_{1} = {Q_{1}^{1}, Q_{2}^{1}, Q_{3}^{1}}where
Q_{1}^{1} = {q_{4}}Q_{2}^{1} = {q_{0}, q_{2}}Q_{3}^{1} = {q_{1}, q_{3}}  Construct ∏_{2 }from ∏_{1} identifying the equivalent states in {Q_{1}^{1}, Q_{2}^{1}, Q_{3}^{1}}.
Q_{1}^{1} cannot be divided as it has only one state.
Q_{2}^{1} and Q_{3}^{1 }has two states each, we need to identify whether they are equivalent. Compare q_{0}, q_{2} on input 0 and 1
both resultant states are same and belong to Q_{3}^{1}.both resultant states are same and belong to Q_{2}^{1}.⇒ q_{0} is 2 equivalent to q_{2}Compare q_{1}, q_{3} on input 0 and 1
both resultant states are same and belong to Q_{2}^{1}.both resultant states are same and belong to Q_{1}^{1}.⇒ q_{1} is 2 equivalent to q_{3}Therefore,
∏_{2} = {Q_{1}^{2}, Q_{2}^{2}, Q_{3}^{2}}Q_{1}^{2} = {q_{4}}Q_{2}^{2} = {q_{0}, q_{2}}Q_{3}^{2} = {q_{1}, q_{3}}  We see that Π_{2} is equal to Π_{1}. The states q_{0} and q_{2} are considered a single state, denoted
q_{02}, and q_{1} and q_{3} are considered a single state, denoted q_{13}. Minimized DFA is
a = 0a = 1→q_{02}q_{13}q_{02}q_{13}q_{02}q_{4}*q_{4}q_{13}q_{4}
2.8.4 Minimization of DFA Using Myhill Nerode Theorem
Myhill Nerode theorem is used if we have to prove the given language is not regular and also to eliminate useless states in the given DFA.
Myhill Nerode Theorem:
 The language L accepted by a DFA is regular if and only if the number of equivalence classes of R_{L} is finite.
 The number of states in the smallest automaton accepting L is equal to the number equivalence classes in R_{L}. Therefore, R_{L} is of finite index.
Let ≡ (equivalence) on the states in M be such that
p ≡ q if and only if, for each input string x, δ(p, x) = δ(q, x) = q_{a}
where q_{a} is accepting state, then we say
⇒ p is equivalent to q or P is not distinguishable from q.
If δ(p, x) = q_{a} and δ(q, x) = q_{n} for some q_{a }∈ F and q_{n} ∉ F then we say
⇒ p is distinguishable from q.
Algorithm for Finding Distinguishable States
 For each pair [p, q] where p ∈ F and q ∈ {Q – F}, mark (p, q) = X
 For each pair of distinct states [p, q] in F X F or (Q − F) X (Q − F) do
 If for some input symbol a δ([p, q], a) = [r, s], if [r, s] = X then
 Mark [p, q] = X
 Recursively mark all unmarked pairs which lead to [p, q] on input for all a ∈ Σ.
 Else
 for all input symbols a do
put [p, q] on the list for δ([p, q], a) unless δ([p, q], a) = [r, r]
Each unmarked pair [p, q] indicates the equivalent states.
Find minimumstate automaton equivalent to the transition diagram given in Figure 2.41.
Fig 2.41 DFA
Solution: The distinguishable states are marked with symbol X. The relation among the states is represented as a matrix of size n × n. If p is distinguishable from q then q is also distinguishable to p and therefore, it is sufficient to have a lower matrix to represent the relation of one state to all other states.
Step 1: First mark for all states [p, q] where state p is final and q is nonfinal.
[d, a] = X 
[d, b] = X 
[d, c] = X 
[d, e] = X 
[d, f ] = X 
[d, g] = X 
[d, h] = X 
Step 2: Find the states that are distinguishable from state a.
δ[a, b], 0) = [b, a] 
δ[a, b], 1) = [a, c] 

δ[a, c], 0) = [b, d] 
δ[a, c], 1) = [a, b] 
⇒mark[a, c] = X as [b, d] = X 
⇒mark[a, b] = X as [a, c] = X 

δ[a, e], 0) = [b, d] 
δ[a, e], 1) = [a, f ] 
⇒mark[a, e] = X as [b, d] = X 
δ[a, f ], 0) = [b, g] 
δ[a, f ], 1) = [a, e] 
⇒mark[a, f ] = X as [a, e] = X 
δ[a, g], 0) = [b, f ] 
δ[a, g], 1) = [a, g] 

δ[a, h], 0) = [b, g] 
δ[a, h], 1) = [a, d] 
⇒mark[a, h] = X as [a, d] = X 
Find the states that are distinguishable from state b
δ[b, c], 0) = [a, d] 
δ[b, c], 1) = [c, b] 
⇒mark[b, c] = X as [a, d] = X 
δ[b, e], 0) = [a, d] 
δ[b, e], 1) = [c, f ] 
⇒mark[b, e] = X as [a, d] = X 
δ[b, f ], 0) = [a, g] 
δ[b, f ], 1) = [c, e] 

δ[b, g], 0) = [a, f ] 
δ[b, g], 1) = [c, g] 
⇒mark[b, g] = X as [a, f ] = X 
δ[b, h], 0) = [a, g] 
δ[b, h], 1) = [c, d] 
⇒mark[b, h] = X as [c, d] = X 
Find the states that are distinguishable from state c
δ[c, e], 0) = [d, d] 
δ[c, e], 1) = [b, f ] 

δ[c, f ], 0) = [d, g] 
δ[c, f ], 1) = [b, e] 
⇒mark[c, f ] = X as [d, g] = X 
δ[c, g], 0) = [d, f ] 
δ[c, g], 1) = [b, g] 
⇒mark[c, g] = X as [d, f ] = X 
δ[c, h], 0) = [d, g] 
δ[c, h], 1) = [b, d] 
⇒mark[c, h] = X as [d, g] = X 
Find the states that are distinguishable from state e
δ[e, f ], 0) = [d, g] 
δ[e, f ], 1) = [f, e] 
⇒mark[e, f ] = X as [d, g] = X 
δ[e, g], 0) = [d, f ] 
δ[e, g], 1) = [f, g] 
⇒mark[e, g] = X as [d, f ] = X 
δ[e, h], 0) = [d, g] 
δ[e, h], 1) = [f, d] 
⇒mark[e, h] = X as [d, g] = X 
Find the states that are distinguishable from state f
δ[f, g], 0) = [g, f ] 
δ[f, g], 1) = [e, g] 
⇒mark[f, g] = X as [e, g] = X 
δ[f, h], 0) = [g, g] 
δ[f, h], 1) = [e, d] 
⇒mark[f, h] = X as [e, d] = X 
Find the states that are distinguishable from state g
δ[g, h], 0) = [f, g] 
δ[g, h], 1) = [g, d] 
⇒mark[g, h] = X as [g, d] = X 
Figure 2.42 shows the lower triangle with the entries computed.
Fig 2.42
From the lower triangle of the matrix it is clear that states [a, g], [b, f ] and [c, e] belong to same class. These states can be merged, and the minimized DFA is
a = 0 
a = 1 

→[a,g] 
[b,f] 
[a,g] 
[b,f] 
[a,g] 
[c,e] 
[c,e] 
[d] 
[b,f] 
*[d] 
[d] 
[a,g] 
[h] 
[a,g] 
[d] 
2.9 Finite Automata with Output
The finite automaton designed so far gives outputs depicting whether the given strings are accepted or not. We can say that the output has only two possibilities, that is ‘yes or no’, But if it is required to have more than two outputs, we can associate the output with either state or transition. If the output is associated with state, the machine is called Moore machine (Figure 2.43(a)), and if the output is associated with transition, the machine is called as Mealy machine (Figure 2.43(b)).
Fig 2.43(a) Moore Machine
Fig 2.43(b) Mealy Machine
The Moore machine machine shown in Figure 2.43(a) gives the output as integer mod 3 for the input represented in binary form. For example, 5 in binary is 101, and the sequence taken on this input is q_{0}, q_{1}, q_{2}, q_{2}. Since it finally is in q_{2} state, the output generated at the end is 2, which is the output corresponding to q_{2} state.
The Mealy Machine in Figure 2.43(b) is designed to generate the output as ‘y’ if current input matches with the previous input, and to output ‘n’ if the input does not match for the input symbols on {ab}*. For input abb, the final output would be ‘y’, and for input aba, the output would be ‘n’.
Note: Moore machine generates output for ɛ, and Mealy machine generates output only on some input symbol.
2.9.1 Moore Machine
Definition 6: A Moore machine is represented as a sixtuple M = {Q, Σ, Δ, δ, λ, q_{0}} where
Q – Set of finite states.
Σ – Set of finite input symbols.
Δ – Set of finite output symbols.
δ – is a mapping function from Q X Σ to Q (i.e. Q X Σ → Q).
λ – is a mapping function which maps Q to Δ (i.e. Q → Δ).
q_{0} – is the initial state.
The state is associated with output. Whenever the Moore machine enters any state, it generates an output associated with that state. If the outputs are only two, then it can be viewed as a special case of finite automata.
2.9.2 Mealy Machine
Definition 7: A Mealy machine is represented as a sixtuple M = {Q, Σ, Δ, δ, λ, q_{0}} where
Q – Set of finite states.
Σ – Set of finite input symbols.
Δ – Set of finite output symbols.
δ – is a mapping function from Q X Σ to Q (i.e. Q X Σ → Q).
λ – is a mapping function which maps Q X Σ to Δ (i.e. Q X Σ → Δ).
q_{0} – is the initial state.
The transition is associated with output. Whenever this machine enters any state on a particular input, it generates output.
Design a Moore machine for inputs that are integer strings represented as binary, and give the output 0 for multiples of 2 and 1 for others.
Solution: Integer numbers, represented as binary, and their corresponding outputs are given below.
Binary representation 
Output 


1 
1 
1 
2 
10 
0 
3 
11 
1 
4 
100 
0 
5 
101 
1 
6 
110 
0 
7 
111 
1 
Let three states be defined by {I, q_{0}, q_{1}} where I is the initial state, q_{0} is a state associated with the output 0 and q_{1} is a state associated with 1. Add path in the automaton such that it enters the corresponding output state on the input sequence and the machine is shown Figure 2.44.
Fig 2.44
Design a Melay machine to generate unary representatio for the given binary representation such that, the number of 0’s in unary is given as N_{u}(0) = N_{b}(0) + 2 * N_{b}(1) if it starts with 1, otherwise N_{u}(0) = 2 * N_{b}(0) + N_{b}(1).
Solution: The Mealy machine requires three states. In the first state (I) on input 0, it changes to state q_{0} indicating that input starts with 0, and on 1 input moves to state q_{1} indicating that input starts with 1. In q_{0} for input 0, it generates output 00, and for input 1, it generates output 0. Similarly in q_{1 }state, for input 0, it generates output 0, and for input 1, it generates output 00. A Mealy machine is shown in Figure 2.45.
Fig 2.45
2.9.3 Equivalence Between Moore and Mealy Machines
Theorem 2: If M_{1} = {Q, Σ, Δ, δ, λ, q_{0}} is a Moore machine, then there is a Mealy machine M_{2} equivalent to M_{1}.
Proof: Let M_{2} = {Q, Σ, Δ, δ, λ`, q_{0}} be a Mealy machine where λ` is defined by
If there is any input x processed in M_{1} that generates a sequence of states q_{1}, q_{2}, ….. q_{n} then the same sequence would be generated in M_{2}.
With each transition, M_{2} emits the output that M_{1} associates with the state entered.
Theorem 3: If M_{1} = {Q, Σ, Δ, δ, λ, q_{0}} is a Mealy machine, then there is a Moore machine M_{2} equivalent to M_{1}.
Proof: Let M_{2} = {{Q × Δ}, Σ, Δ, δ`, λ`, [q_{0}, b_{0}]}where b_{0} is an arbitrarily selected member of Δ. Let the states in M_{2} be pairs [q, b] where q ∈Q and b∈Δ.
Let δ` be defined by δ`([q, b], a) = [δ(q, a), λ(q, a)].
Let λ` be defined by λ`([q, b]) = b.
Using induction it can be shown that M_{2} can simulate all the moves of M_{1 }i.e if M_{1} enter states sequence as q_{0}, q_{1}, q_{2}, ….. q_{n} on input a_{1}, a_{2}, a_{3} …… a_{n} and emits output b_{1}, b_{2}, …… b_{n}, then M_{2} enters states [q_{0}, b_{0}], [q_{1}, b_{1}], [q_{2}, b_{2}]…… [q_{n}, b_{n}] and emits outputs b_{0}, b_{1}, b_{2}, …..b_{n}.
2.9.4 Interconversions Between Machines
Construct a Moore machine for the following Mealy machine.
Solution:
 Frame the possible states of the form [q a] where q ∈Q and a ∈Δ. The number of states generated would be n × m where n is the number of states in Q and m is the number of output symbols, and out of these states, only few would be necessary. To include only the required ones, first identify the state q_{i} which is associated with different outputs.
 Represent of q_{i} as different states, such that the number of states is equal to the number of different outputs associated with q_{i}.
 Reconstruct the table with new states.
 Construct its equivalent Mealy machine.
 If the initial state is associated with output then create a new state and add the transitions similar to initial state q_{1} and add the output as ɛ.
Step 1: In the given table, q_{1} and q_{3} are associated with only one output. But q_{2} and q_{4} are associated with two different outputs.
Step 2: Represent q_{2} as two states as q_{20} and q_{21}, represent q_{4} as two states q_{40} and q_{41}.
Step 3: Reconstruct the table with new states.
Step 4: Construction of equivalent Moore machine.
Step 5: Since q_{1 }state is associated with output 1 add a new initial state q_{0} and associate with it the transitions of q_{1}, but with output ɛ.
Construct the Mealy machine for the given Moore machine.
Solution:
We construct the Mealy machine by associating the output with transition. The resultant table is
We observe that the transitions corresponding to q_{2} state and q_{3} state are same. Hence, we can eliminate q_{3} state and modify the Mealy machine to
2.10 Applications of Finite Automata with Output
Moore machines are useful to describe language recognizers, to describe counters, such as a modulo4 counter. Mealy machines are useful to describe DFA in which an output is associated with the transition. A fulladder changes the states to reflect the carryin, and it outputs the sum as the transition takes place.
2.10.1 The Fulladder
Moore machine: Here we use the carryin as the state. The DFA will output the sum, but this example will ignore that and focus on the state transitions.
Note that a twostate Moore machine does not easily display the sum.
A complete Moore machine model of a fulladder would require four states.
q_{0} 
CarryIn = 0 
Sum = 0 
q_{1} 
CarryIn = 0 
Sum = 1 
q_{2} 
CarryIn = 1 
Sum = 0 
q_{3} 
CarryIn = 1 
Sum = 1 
Mealy machine:
To simplify the definition, let Q = {q_{0}, q_{1}}, where
q_{0} is the state previously labelled as ‘CarryIn = 0’ and
q_{1} is the state previously labelled as ‘CarryIn = 1’.
The input alphabet is Σ = {<0, 0>, <0, 1>, <1, 0>, <1, 1>}.
Please note that this alphabet has four symbols.
The output alphabet is Δ = {0, 1}.
The transition function: 
δ(q_{0}, <0, 0>) = q_{0} 
δ(q_{1}, <0, 0>) = q_{0} 
δ(q_{0}, <0, 1>) = q_{0} 
δ(q_{1}, <0, 1>) = q_{1} 

δ(q_{0}, <1, 0>) = q_{0} 
δ(q_{1}, <1, 0>) = q_{1} 

δ(q_{0}, <1, 1>) = q_{1} 
δ(q_{1}, <1, 1>) = q_{1} 
The output function: 
λ(q_{0}, <0, 0>) = 0 
λ (q_{1}, <0, 0>) = 1 
λ (q_{0}, <0, 1>) = 1 
λ (q_{1}, <0, 1>) = 0 

λ (q_{0}, <1, 0>) = 1 
λ (q_{1}, <1, 0>) = 0 

λ (q_{0}, <1, 1>) = 0 
λ (q_{1}, <1, 1>) = 1 
Fig 2.46
Fig 2.47
2.10.2 The String Sequence Detector
We now investigate two implementations of a 11011 sequence detector.
Each of these machines accepts strings, one symbol at a time.
The alphabet for each machine is Σ = {0, 1}.
Each machine will accept any string with a fivesymbol suffix 11011.
Moore machine: Let Q = {q_{1}, q_{2}, q_{3}, q_{4}, q_{5}, q_{6}} where q_{1 }is the start state, Σ = {0, 1} F = {q_{6}}
The transition function is given by the following equations.
Fig 2.48
Mealy machine: Here the input and output alphabets are considered same.
Q = {q_{1}, q_{2}, q_{3}, q_{4}, q_{5}} where q_{1} is the start state
Σ = {0, 1}
Δ = {0, 1}
Fig 2.49
The transition function is given by the following:
 δ(q_{1}, 0) = q_{1}, δ(q_{2}, 0) = q_{1}, δ(q_{3}, 0) = q_{4}, δ(q_{4}, 0) = q_{1}, δ(q_{5}, 0) = q_{1},
δ(q_{1}, 1) = q_{2}, δ(q_{2}, 1) = q_{3}, δ(q_{3}, 1) = q_{3}, δ(q_{4}, 1) = q_{5}, δ(q_{5}, 1) = q_{1}.The output function is given by the following:
 l (q_{1}, 0) = 0, λ (q_{2}, 0) = 0, λ (q_{3}, 0) = 0, λ (q_{4}, 0) = 0, λ (q_{5}, 0) = 0,
λ (q_{1}, 1) = 0, λ (q_{2}, 1) = 0, λ (q_{3}, 1) = 0, λ (q_{4}, 1) = 0, λ (q_{5}, 1) = 1.
Solved Problems
Problem 1: Consider a toy game shown in Figure 2.50. A marble is dropped in at A or B. Levers X_{1}, X_{2}, X_{3 }cause the marble to fall either to the left or right. Whenever a marble encounters a lever, marble causes the lever to change state, so that the next marble to encounter the lever will take the opposite branch.
Model this toy by an FA. Denote marble input at A by input 0 and a marble input at B by input 1. A sequence of inputs is accepted if the last marble comes out at D. Describe the set accepted by FA.
Fig 2.50
Solution: This problem can be modelled using finite automata in which each lever has two possible moves, that is, L for left and R for right. We assume that 0 indicates the marble is dropped from A and 1 indicates that the marble is dropped from B. Initially in the start state, it is assumed that all levers are towards left, indicated by state LLL (for positions of X_{1}, X_{2 }and X_{3}, respectively). If the marble is dropped from A only X_{1} would change from L to R and if the marble is dropped from B then the lever X_{2},_{ }X_{3} would change to R. The change of lever states is shown in the following table.
Note: Marble coming out of D wins the game.
Set of accepting states are * marked.
Problem 2: Design an FA that accepts strings in L such that integer number ‘a’ when represented in binary form is divisible by 3.
Solution: It is required to construct a DFA such that any integer in binary form that is divisible by 3 should enter into final state on seeing the last digit.
When we divide any number by 3, there are three possible remainders 0, 1 or 2. So, it is required to have three states to indicate each possibility. So, let
q_{0}  represent remainder 0
q_{1}  represent remainder 1
q_{2}  represent remainder 2. The states are shown in the Figure 2.51
Fig 2.51
Since the number should be divisible by 3, which gives the remainder as zero, the state q_{0} is made as final state.
Problem 3: Design DFA that accepts all strings with 0’s and 1’s such that any five consecutive symbols have at least two 0’s.
Solution: This problem can be solved by keeping track of the previous four symbols and the current symbol. We make an assumption that the string would have at least a length of five symbols to be accepted. This requires many states shown below. We use a special state D to indicate a dummy state. The minimum length of string is assumed to be of length 5.
Note: The suffix of every state keeps track of the sequence of symbols seen so far.
Problem 4: Design a DFA that accepts the set of all strings beginning with 1 (which, interpreted as binary representation of an integer, is congruent to zero modulo 5).
Solution: Possible outputs with modulo 5 operation are 0, 1, 2, 3, 4. Let these states be denoted by q_{0} q_{1} q_{2} q_{3} q_{4} (representing remainders 0, 1, 2, 3, 4, respectively). It is also said that the string should begin with 1. If the string starts with 0 it should not be accepted. Hence, 0 is not a valid integer in the set. So on seeing 0, it should enter into a dummy state. Add a new initial state S and a dummy state q_{d}. Figure 2.52 shows the designed DFA.
Fig 2.52 DFA for Integer Mod 5
Problem 5: Design a DFA to accept strings having 111 as substring.
Solution: The language has strings which are of the form {111, 0111, 1111, 1110, 00111, 01111, 10111, 11111,………….}. The DFA should have four states. In the 0^{th} state, if it finds 1, it changes to 1^{st} state. In 1^{st} state if it finds 1, it changes to 2^{nd} state. In 2^{nd} state if it finds 1, it changes to 3^{rd} state. Declare 3^{rd} state as final and be in the same state on 0 or 1. In states other than the 3^{rd}, if it finds 0, it should start from initial state as there would not be 111’s. The DFA is shown in Figure 2.53.
Fig 2.53 DFA for Problem 5
Problem 6: Design DFA for L(M) = {a^{n}b  n ≥ 0}
Solution: Start with initial state q_{0}. Define a^{n} by taking loop. To have b next, have another state q_{1}.The transitions on q_{1} can be defined to move on to dummy state q_{2}.
Fig 2.54 DFA for Strings with a’s Followed by a b
Problem 7: Design DFA to accept set of all strings ending in 00.
Solution: The language has strings which are of the form {00, 100, 000, 0000, 1000, 0100, 1100, ……}. The DFA should have three states. In the 0^{th} state, if it finds 0, it changes to 1^{st} state. In 1^{st} state if it finds 0, it changes to 2^{nd} state. Declare 2^{nd} state as final and be in the same state on 0. In any state, if it finds 1, it should change to initial state as it should end with 00. The DFA is shown Figure 2.55.
Fig 2.55 DFA for Strings Ending with 00
Problem 8: Design DFA to accept the set of all strings not containing 101 as substring.
Solution: The language has strings of the form {e, 0, 1, 00, 10, 01, 11, 001,.}. It should not contain strings that have 101 as substring. First define DFA with four states with 101 string. Declare the last state q_{3} as dead state. The remaining states can be declared as final states as it has to accept strings of length 0, 1, 2,…. The moves on each state are defined as shown in Figure 2.56.
Fig 2.56 DFA for String with Substring 101
Problem 9: If L(M) = {0^{m }1^{n}  m, n ≥ 0}, design DFA for M.
Solution: Strings of the form {ɛ, 0, 1, 00, 01, 11, 000, 001, 011, 111, 0000, 0001, 0011, 0111, 1111,….} are valid in the language. Since ɛ is valid, initial state is declared as final state. It stays in the same state q_{0} on 0’s and changes to q_{1} on 1. Declare q_{1} as final state.
Be in q_{1} state on 1 and move to dead state q_{2} on 0. Be in this same state whether on 0 or on 1, as they are invalid strings.
Fig 2.57 DFA for Strings with 0’s Followed by 1’s
Problem 10: Design DFA to accept the set of all strings containing three consecutive 0’s.
Solution: The language has strings of the form {000, 1000, 0000, 0001, 11000, 10000, 01000, 00000,………….}. The DFA should have four states. In the 0^{th} state, if it finds 0, it changes to 1^{st} state. In 1^{st} state, if it finds 0, it changes to 2^{nd} state. In 2^{nd} state, if it finds 0, change to 3^{rd} state. Declare 3^{rd} state as final and be in the same state on 1 or 0. In states other than the3^{rd}, if it finds 1, it should start from initial state as there would not be 000’s. The DFA is shown in Figure 2.58.
Fig 2.58 DFA for Strings with Three Consecutive 0’s
Problem 11: Design DFA that accepts even number of a’s or even number of b’s.
Solution: The language has strings which are of the form {aa, bb, abb, bab, bba, aab, aba, aab,….}. The DFA should have four states. q_{0} indicates the condition where number of a’s and b’s are even. q_{2} indicates the condition where number of a’s is even and number of b’s is odd. q_{1} indicates that number of b’s is even and number of a’s is odd, and q_{4} indicates that number of a’s is odd and, further, number of b’s is also odd. The DFA is shown in
Fig 2.59 DFA for Even Number of a’s or b’s
Problem 12: Design the NFA that accepts 1100 only.
Solution: The NFA for the given condition can be drawn in many ways. Samples are shown in Figure 2.60.
Fig. 2.60 DFA for String 1100
Problem 13: Design the NFA that accepts strings that contains either two consecutive 0’s or two consecutive 1’s.
Solution: The language has strings of the form {00, 11, 000, 100, 001, 110, 011, 111…}
Therefore, whether on two consecutive 0’s or 1’s, go to state q_{3} using q_{1} or q_{2}. In q_{0} and q_{3} states, define moves to be in the same state on 0/1 as shown in Figure 2.61.
Fig. 2.61 DFA for 00 or 11
Problem 14: Design the NFA to accept (a) all strings containing 1100 as substring or (b) the set of all strings in which a pair of 1’s is followed by a pair of 0’s.
Solution:
Fig. 2.62 NFA for Substring 1100
DFA is difficult to construct, but it is fast in processing strings. NFA is easy to construct, but it is slow in processing. Hence, it is always desirable to construct the NFA and convert it to a DFA, as for every NFA that accepts L three exists an equivalent DFA that accepts the same L and is shown in Figure 2.62.
Problem 15: Convert the following NFA to DFA.
δ 
0 
1 
→p 
{pq} 
p 
q 
r 
r 
r 
s 
 
*s 
s 
s 
Solution: Start with initial state: find transitions. Whenever you get new set of states, add it to set of states and find transitions on input symbols.
δ 
0 
1 
→[p] 
[pq] 
[p] 
[pq] 
[pqr] 
[pr] 
[pr] 
[pqs] 
[p] 
[pqr] 
[pqrs] 
[pr] 
*[pqs] 
[pqrs] 
[prs ] 
*[pqrs] 
[pqrs] 
[prs ] 
*[prs] 
[pqs] 
[ps] 
*[ps] 
[pqs] 
[ps] 
Problem 16: Design NFA for language L(M) = 01*0*1.
Solution: The strings are of the form: 0 followed by zero or more 1’s, followed by zero or more 0’s but ending with 1.
Fig. 2.63 NFA for Problem 16
Problem 17: Design NFA for language L(M) = 01*  0*1.
Solution: The language has strings {0, 01, 011, 0111 …..} ∪ {1, 01, 001, 0001,….}.
This can be drawn in two ways as shown in Figure 2.64:
Fig. 2.64 Two Possible Ways of Drawing NFA for 10* / 0*1
Problem 18: Find whether the following two are equivalent or not.
Fig. 2.65
Solution: Equivalence of two automata (i.e. if they accept same language):
 Two FAs over ∑ are equivalent if they accept the same set of strings over ∑.
 When two FAs are not equivalent, there exists some string w over ∑ for which, one automaton reaches a final state on w whereas the other reaches a nonfinal state.
we can simplfy DFA in Figure 2.65(a) by removing state q_{5} as it is not reachable.
Current State (M1, M2) 
Next state (M1, M2) 


0 
1 

→(q_{0}, q_{1}^{
1}) 
(q_{1}, q_{2}^{
1}) 
(q_{3}, q_{2}^{
1}) 
(q_{1}, q_{2}^{
1}) 
(q_{3}, q_{2}^{
1}) 
(q_{2}, q_{3} ^{1}) 
(q_{3}, q_{2}^{
1}) 
(q_{3}, q_{2}^{
1}) 
(q_{4}, q_{3}^{
1}) 
(q_{2}, q_{3}^{
1}) 
(q_{2}, q_{3}^{
1}) 
(q_{2}, q_{3}^{
1}) 
(q_{4}, q_{3}^{
1}) 
(q_{4}, q_{3}^{
1}) 
(q_{4}, q_{3}^{
1}) 
It is observed that for all pairs (p, q), where p ∈ states in Figure 2.65(a) and q ∈ states in Figure 2.65(b), they both either go to nonfinal state or final state. Hence, these two are said to be equivalent.
We can simplify state q_{5} not reachable.
Problem 19: Reduce the DFA shown in Figure 2.66.
0 
1 

→1 
2 
3 
2 
4 
5 
3 
6 
7 
4 
4 
5 
5 
6 
7 
*6 
4 
5 
7 
6 
7 
Fig. 2.66
Here in this problem equivalent classes are named using alphabets A, B, C ...
Solution:
∏_{0} {A, B} = {{6}, {1, 2, 3, 4, 5, 7}}
∏_{1} {A, C, D} = {{6}, {1, 2, 4}, {3, 5, 7}}
∏_{1} {A, C, D} = {{6}, {1, 2, 4}, {3, 5, 7}}
0 
1 

→{1, 2, 4} 
{1, 2, 4} 
{3, 5, 7} 
{3, 5, 7} 
{6} 
{3, 57} 
*{6} 
{1, 2, 4} 
{3, 5, 7} 
Fig. 2.67
The language accepted by this DFA is set of all strings of 0's and 1' is that end with 10.
Problem 20: Minimize the DFA shown in Figure 2.68.
a 
b 

→ Q_{0} 
Q_{1} 
Q_{0} 
Q_{1} 
Q_{0} 
Q_{2} 
Q_{2} 
Q_{3} 
Q_{1} 
*Q_{3} 
Q_{3} 
Q_{0} 
Q_{4} 
Q_{3} 
Q_{5} 
Q_{5} 
Q_{6} 
Q_{4} 
Q_{6} 
Q_{5} 
Q_{6} 
Q_{7} 
Q_{6} 
Q_{3} 
Fig. 2.68
Solution:
∏_{0} {1, 2} = {q_{3}} {q_{0} q_{1} q_{2} q_{4} q_{5} q_{6} q_{7}}
∏_{1} {1, 3, 4, 5} = {q_{3}} {q_{0} q_{1} q_{5} q_{6}} {q_{2} q_{4}} {q_{7}}
∏_{2} {1, 4, 6, 7} = {q_{3}} {q_{0} q_{6}}{q_{2} q_{4}} {q_{1} q_{5}} {q_{7}}
∏_{3} {1, 4, 6,7} = {q_{3}} {q_{0 }q_{6}} {q_{2 }q_{4}} {q_{1} q_{5}} {q_{7}}
a 
b 

→Q_{0,6} 
Q_{1,5} 
Q_{0,6} 
Q_{1,5} 
Q_{0,6} 
Q_{2,4} 
Q_{2,4} 
Q_{3} 
Q_{1,5} 
*Q_{3} 
Q_{3} 
Q_{0,6} 
Fig. 2.69
Note: If the DFA in Figure 2.68 is observed carefully, it is clear that the states Q_{4}, Q_{5}, Q_{6} and Q_{7} are not reachable from Q_{0} state they can be eliminated directly.
Problem 21: Minimize the finite automata given in Figure 2.70.
Fig. 2.70
Solution: Let us represent the DFA as a transition table.
a = a 
a = b 

→q_{0} 
q_{3} 
q_{5} 
q_{1} 
q_{0} 
q_{6} 
q_{2} 
q_{1} 
q_{3} 
q_{3} 
q_{5} 
q_{4} 
q_{4} 
q_{6} 
q_{4} 
*q_{5} 
q_{2} 
q_{5} 
*q_{6} 
q_{2} 
q_{6} 
 Initially we identify 0equivalence as ∏_{0} = {Q_{1}^{0}, Q_{2}^{0}} where Q_{1}^{0} is set of final states and Q_{2}^{0} = Q − Q_{1}^{0 }is set of nonfinal states.
Q_{1}^{0} = {q_{5}, q_{6}}
Q_{2}^{0} = {q_{0}, q_{1}, q_{2}, q_{3}, q_{4}}
 Construct ∏_{1 }from ∏_{0} identifying the equivalent states in {Q_{1}^{0}, Q_{2}^{0}}.
Q_{1}^{0} has two states and Q_{2}^{0} has five states, and we need to identify whether they are 1equivalent.
Compare q_{5}, q_{6} on inputs a and b.
both resultant states belong to Q_{2}^{0}.both both resultant states belong to Q_{1}^{0}.⇒ q_{5} is 1equivalent to q_{6} hence Q_{1}^{0 }cannot be divided.
Compare q_{0}, q_{1} on inputs a and b.
both resultant states belong to Q_{2}^{0}.both resultant states belong to Q_{1}^{0}.⇒ q_{0} is 1equivalent to q_{1}.
Compare q_{0}, q_{2} on inputs a and b.
both resultant states belong to Q_{2}^{0}.^{}these two states belong to different sets in ∏_{0}.⇒ q_{0 }is not 1equivalent to q_{2}. Hence Q_{2}^{0} is split into two sets.
Compare q_{0}, q_{3} on inputs a and b.
these two states belong to different sets in ∏_{o}these two states belong to different sets in ∏_{o}⇒ q_{0 }is not 1equivalent to q_{3 }
Compare q_{0}, q_{4} on input a and b.
these two states belong to different sets in ∏_{o}these two states belong to different sets in ∏_{o}⇒ q_{0 }is not 1equivalent to q_{4 }
Therefore, ∏_{1} = {Q_{1}^{1}, Q_{2}^{1}, Q_{3}^{1}}
where
Q_{1}^{1} = {q_{5}, q_{6}}
Q_{2}^{1} = {q_{0}, q_{1}}
Q_{3}^{1} = {q_{2}, q_{3}, q_{4}}
 Construct ∏_{2 }from ∏_{1}, identifying the equivalent states in {Q_{1}^{1}, Q_{2}^{1}, Q_{3}^{1}}.
Q_{1}^{1} and Q_{2}^{1} have two states, and Q_{3}^{1 } has three states. We need to identify whether they are 2equivalent.
Compare q_{5}, q_{6} on inputs a and b.
both resultant states belong to Q_{3}^{1}.both resultant states belong to Q_{1}^{1}.⇒ q_{5 }is 2equivalent to q_{6},Hence Q_{1}^{1 }cannot be divided.
Compare q_{0}, q_{1} on inputs a and b.
these two states belong to different sets in ∏_{1}both resultant states belong to Q_{1}^{1}.⇒ q_{0} is not 2equivalent to q_{1 }
Compare q_{2}, q_{3} on inputs a and b.
these two states belong to different sets in ∏_{1}both resultant states belong to Q_{3}^{1}.⇒ q_{2 }is not 2equivalent to q_{3}.
Compare q_{2}, q_{4} on inputs a and b.
these two states belong to different sets in ∏_{1}both resultant states belong to Q_{3}^{1}.⇒ q_{2} is not 2equivalent to q_{4}.
Therefore, ∏_{2} = {Q_{1}^{2}, Q_{2}^{2}, Q_{3}^{2}, Q_{4}^{2}, Q_{5}^{2}},
where
Q_{1}^{2} = {q_{5}, q_{6}}
Q_{2}^{2} = {q_{0}}
Q_{3}^{2} = {q_{1}}
Q_{4}^{2} = {q_{2}}
Q_{5}^{2} = {q_{3}, q_{4}}
 Construct ∏_{3 }from ∏_{2}, identifying the equivalent states in {Q_{1}^{2}, Q_{2}^{2}, Q_{3}^{2}, Q_{4}^{2}, Q_{5}^{2}}.
Q_{1}^{2}, Q_{5}^{2} have only a single state. Hence, these sets cannot be divided.Q_{1}^{2} and Q_{5}^{2} have two states; we need to identify whether they are 3equivalent.
Compare q_{5}, q_{6} on inputs a and b.
both resultant states belong to Q_{4}^{2}.both resultant states belong to Q_{1}^{2}.⇒ q_{5} is 3equivalent to q_{6} Q_{1}^{1 }cannot be divided.
Compare q_{3}, q_{4} on inputs a and b.
both resultant states belong to Q_{1}^{2}.δ(q3, b) = q4δ(q4, b) = q4.⇒ q_{3} is 3equivalent to q_{4}
Therefore, ∏_{3} = {Q_{1}^{3}, Q_{2}^{3}, Q_{3}^{3}, Q_{4}^{3}, Q_{5}^{3}},
where
Q_{1}^{1} = {q_{5}, q_{6}}
Q_{2}^{1 }= {q_{0}}
Q_{3}^{1 }= {q_{1}}
Q_{4}^{1 }= {q_{2}}
Q_{5}^{1} = {q_{3}, q_{4}}
 We see that ∏_{3} is equal to ∏_{2}. The states q_{5 }and q_{6 }are considered as the single state q_{56}, and q_{3 }and q_{4} are considered as the single state q_{34}. Minimized DFA is
a = aa = b→q_{0}q_{34}q_{56}q_{1}q_{0}q_{56}q_{2}q_{1}q_{34}q_{34}q_{56}q_{34}*q_{56}q_{2}q_{65}
Problem 22: Construct Moore machine for the following Mealy machine (Figure 2.71).
Fig. 2.71
Solution:
In the given table, all states are associated with only one output. No state needs to be split as all states are with one output.
Equivalent Moore Machine
Problem 23: Give Mealy and Moore machine for input from (0+1)* satisfying the given condition. If input ends with 101, output is A if input ends with 110, output is B; otherwise output is C.
Solution: For this problem, it is easy to construct Moore machine and then convert it into its equivalent Mealy machine.
Fig. 2.72
Its corresponding Mealy machine is as follows.
Problem 24: Give Mealy and Moore machines for input from (0 + 1 + 2)* to print the residue modulo 5 of the input treated as a ternary (base 3, with digits 0, 1, 2) numbers.
Solution: To construct the Moore machine we have to understand the possible outputs. Since it is residue modulo 5, the possible outputs are 0, 1, 2, 3 and 4. The possible inputs would be the ternary representations of the integers.
Example:
Integer number 
Ternary representation 
Output 

1 
1 
1 
2 
2 
2 
3 
10 
3 
4 
11 
4 
5 
12 
0 
6 
20 
1 
7 
21 
2 
8 
22 
3 
9 
100 
4 
10 
101 
0 
11 
102 
1 
12 
110 
2 
13 
111 
3 
14 
112 
4 
The Moore machine is given in Figure 2.73.
Fig. 2.73
The corresponding Mealy machine is
Problem 25: Draw a DFA to accept strings with a’s and b’s such that the number of a’s is a multiple of 3 and the number of b’s is a multiple of 2.
Solution: To construct a DFA satisfying both conditions, first let us construct DFAs independent of each condition and then merge them to get the final DFA.
 a’s in multiples of 3 (Figure 2.74):
Fig. 2.74
 b’s in multiples of 2 (Figure 2.75):
Fig. 2.75
To construct a DFA satisfying both the conditions, merge the two DFAs.
The states in the final DFA are {[AX], [AY], [AZ], [BX], [BY], [BZ], [CX], [CY], [CZ], [DX], [DY], [DZ]}
The state which satisfies both the conditions is [DZ]. To find the transitions of the DFA, start at the initial state [AX]. The transitions are defined as follows:
δ([PQ], a) = [ δ(P, a) δ(Q, a)] where P is a state of the 1^{st} DFA and Q is a state of the 2^{nd} DFA.
i = a 
i = b 


→[AX] 
[BX] 
[AY] 
[AY] 
[BY] 
[AZ] 
[AZ] 
[BZ] 
[AY] 
[BX] 
[CX] 
[BY] 
[BY] 
[CY] 
[BZ] 
[BZ] 
[CZ] 
[BY] 
[CX] 
[DX] 
[CY] 
[CY] 
[DY] 
[CZ] 
[CZ] 
[DZ] 
[CY] 
[DX] 
[BX] 
[DY] 
[DY] 
[BY] 
[DZ] 
*[DZ] 
[BZ] 
[DY] 
Fig. 2.76
Problem 26: Construct the DFA for the following NFA with ɛ moves:
Solution:
Step 1: Compute ɛclosure of each state.
Step 2: Explore the valid states in DFA that are computed in step 2.
Similarly, we compute for every new state that appears, and the computed values are used to get the following table:
a = 0 
a = 1 

→ɛ*(q_{0}) 

=* [q_{0} q_{1} q_{2}] 
[q_{2} q_{4}] 
[q_{3}] 
*[q_{2} q_{4}] 
[q_{2}] 
[q_{3} q_{4}] 
* [q_{3}] 
[∅] 
[∅] 
[q_{2}] 
[q_{2}] 
[q_{3}] 
[*[q_{3} q_{4}] 
[∅] 
[q_{4}] 
[q_{4}] 
[∅] 
[q_{4}] 
[∅] 
[∅] 
[∅] 
Transition diagram for DFA is shown in the following figure:
Problem 27: Convert the following NFA with ɛ to DFA.
Step 1: Compute ɛclosure of each state.
Step 2: Explore the valid states in DFA that are computed in step 2.
i/p = a 
i/p = b 


→ɛ*(A) 
[ABCDE] 
[DE] 
=[ABD] 

[ABCDE] 
[ABCDE] 
[BDE] 
[DE] 
[E] 
[D] 
[BDE] 
[CE] 
[DE] 
[E] 
[Ø] 
[Ø] 
[D] 
[E] 
[D] 
[CE] 
[Ø] 
[B] 
[Ø] 
[Ø] 
[Ø] 
[B] 
[C] 
[E] 
[C] 
[Ø] 
[B] 
Transition diagram for DFA is shown in the following figure:
Summary
 Finite Automata can be represented as a 5tuple, transition table or transition diagram.
 FA can be used as language acceptor.
 For every NFA with ɛ, we can construct a NFA without ɛ.
 We can construct equivalent DFA for any NFA.
 Two finite automata are said to equivalent if the language accepted by the two machines is same.
 Number of states in FA can be minimized by Myhill Nerode theorem or by π constructions method.
 Moore and Mealy machines are the special finitestate machines with output.
 In Moore machine, output is associated with state.
 In Mealy machine, output is associated with state and input.
Short Answers
 What is a finite automaton? Give two examples.
Answer: Finite automaton is a mathematical model of a system consisting of finite set of state, set of transition from state to state that occurs on input symbols from alphabet.
Examples: Text editorand lexical analyser are examples.
 Enumerate the differences between NFA and DFA.
Answer: DFA has moves welldefined on the current state and current input symbol. In NFA, the moves are not well defined. In NFA, multiple moves are defined either on ɛ or single input symbol.
 List any four ways of theorem proving. (Nov 2007)
Answer: The four ways of theorem proving are
 Proof by induction
 Proof by contradiction
 Proof by transposition
 Proof by construction
 What is meant by equivalent states in DFA? (Nov 2007)
Answer: Definitions 4 and 5 of Section 1.8.2.
 Define automata.
Answer: Definition 1 of Section 1.2.
 What is the principle of mathematical induction?
Answer: See Section 1.1
 Construct a DFA, over Σ = {a, b}, that produces not more than 3 a’s.
Answer: See Example 14.
 Define the languages accepted by NFA and DFA
Answer: Language of DFA A = {Q, ∑, δ, q_{0}, F}is defined by
{w  δ`(q_{0}, w) = P for some P in F}Language of NFA A = {Q, ∑, δ, q_{0}, F}is defined by
{w  δ`(q_{0}, w) ∩ F ≠ ∅}; that is, there is at least one final state in the resultant set.
Fill in the Blanks
 The number of states in DFA is _______________ than the number of states in NFA for the same language.
 The transition function for NFA is a mapping function given as _____________.
 The transition function for DFA is a mapping function given as ______________.
 The finite automata to recognize n words each of maximum length m require ____________ states.
 The time required to process a string of length x by NFA with N states is __________ compared to the time required by a DFA for the same language.
 The minimum number of states required to accept the language L = {w/w ∈ (a + b)*} is _____________ .
 The minimum number of states required to accept the language L = {xay/x, y∈ (a + b)*} is _____________ .
 Finite automata for accepting words ‘this’ and ‘that’ require _______ states.
 ________________ of a state is the set of states that can be reached by etransitions.
 NFA with ɛ can increase the processing time of NFA (True/False).
 Elimination of ɛedges from NFA increases___________.
 The two states q_{1 }and_{ }q_{2 }are said to be _________ if both δ (q_{1},_{ }a) and (q_{2},a) reach final states or both of them reach nonfinal states for all a ∈ ∑.
 The output in ________________ machine is associated with transition.
 All Moore machines have an equivalent finite automata (True/False).
 For every finite automaton, there is always an equivalent Moore and Mealy machines (True/False).
Answers
 greater.
 Q × Σ to 2^{Q}
 Q × Σ to Q
 2^{mn}
 less
 one
 two
 seven
 epsilon closure
 true
 number of edges
 equivalent
 Melay
 False
 True
Objective Question Bank
 FA has
 Unlimited memory
 No memory at all
 Limited Memory
 none of the above
 Consider the following deterministic finitestate automaton M:
Let S denote the set of fourbit binary strings in which the first is 0 and fourth is 0. Find the number of strings in S that are accepted by M. It is
 2
 5
 7
 8
 How many twostate FAs can be drawn over the alphabet {0, 1} to accept an empty language ?
 12
 14
 20
 15
 How many twostate FAs can be drawn over the alphabet {0, 1} to acept the language (0+1)^{*}
 12
 14
 20
 15
 The smallest FA that accepts the language {x/length of x is divisible by 3} has
 2 states
 3states
 4 states
 5 states
 How many DFAs exist with two states over the input alphabet (a, b)?
 16
 26
 32
 64
 How many DFAs exist with three states over the input alphabet {0, 1}?
 144
 6561
 5832
 729
 The recognizing capabilities of NDFSM and DFSM
 may be different
 must be different
 must be same
 none of the above
 What is the minimum number of states of the NFA that accepts the language {abab^{n}  n≥0} U {aba^{n}  n ≥ 0}?
 4
 3
 5
 9
 What is the minimum number of states in the NFA accepting the language{ab, abc}?
 4
 5
 3
 2
 Consider the NFA M shown below:
Let the language accepted by M be L. Let L_{1} be the language accepted by the NFA M_{1} obtained by changing nonaccepting states of M to accepting states. Which of the following statements is true?
 L_{1} = {0, 1)^{*} – L
 L_{1} = {0, 1}^{*}
 L_{1 }≠ L
 L_{1} = L
 The basic limitation of FSM is that
 It cannot remember arbitrarily large amount of information.
 It sometimes recognizes grammars that are not regular.
 It sometimes fails to recognize grammars that are regular.
 All of the above comments are true.
 Given an arbitrary NFA with N states, the maximum number of states in an equivalent minimized DFA is at least
 N^{2}
 N
 2^{N}
 N!
 The FSM pictured below recognized
 all strings
 no string
 ɛ alone
 None of the above
 The number of states of the FSM required to simulate the behaviour of a computer, with a memory capable of storing ‘m’ words, each of length ‘n’ bits, is
 m × 2^{n}
 2^{mn}
 2^{m }^{+}^{ n}
 None of the above.
 Consider the following 2DFA ({q_{0}, q_{1}, q_{2}, q_{3},_{ }q_{4}}, {0, 1}, δ q_{0}, {q_{2}}), where δ is
01→q_{0}q_{0}, Rq_{1}, Rq_{1}q_{1}, Rq_{2}, R* q_{2}q_{2}, Rq_{3}, Lq_{3}q_{4}, Lq_{3}, Lq_{4}q_{0}, Rq_{4}, L
Which of the following strings is accepted by the above FA?
 1100011001000
 1100000000111
 1000001110000
 1100001100110
 Choose the incorrect statement
 Moore and Melay machines are FSMs with output capability.
 Any given Moore machine has an equivalent Melay machine.
 Any given Melay machine has an equivalent Moore machine.
 Moore machine is not a FSM.
 The major difference between Moore and Melay machines is that
 The output of the former depends on the present state and present input.
 The output of the former depends only on the present state.
 The output of the former depends only on the present input.
 None of the above.
 An FSM with output capability can be used to add two given integers in binary representation. This is
 True
 False
 May be true
 None of the above
 A finitestate machine has a single input x, single output Z and the following statetable:
Present stateNext state, Zx = 0x = 1AD, 0B, 0BB, 1C, 1CB, 0D, 1DB, 1C, 0
If the initial state is unknown, then the shortest input sequence to reach the final state C is
 01
 10
 101
 110
 The finitestate machine described by the following state diagram with A as starting state, where an arc label is denoted by x/y (x stands for 1bit input and y stands for 2bit output).
 Outputs the sum of the present previous bits of the input.
 Outputs 01 whenever input sequence contains 11.
 Outputs 00 whenever input sequence contains 10.
 None of the above.
 Let (Me)^{2} mean that given a Melay machine, an input string is processed and then the output string immediately is fed into the machine (as input) and reprocessed. Only this second resultant output is considered the final output of (Me)^{2}. If the final output string is the same as the original input string, we say that (Me)^{2} has an identity property. Symbolically, we write (Me)^{2} = identity. Consider the following machines.
Which of the above machines have the identity property?
 i) only
 i) and ii) but not iii)
 i) and iii) but not ii)
 All have identity property.
 Let (Me_{1}) (Me_{2}) mean that an input string is processed on Me_{1} and then the output string is immediately fed into Me_{2} (as input) and reprocessed. Only this second resultant output is considered the final output of (Me_{1})(Me_{2}). If the output string is the same as the original input string, we say that (Me_{1})(Me_{2}) has the identity property, symbolically written (Me_{1})(Me_{2}) = identity. Consider following machines.
Which of the following is most appropriate?
 (Me_{1})(Me_{2}) = (Me_{2})(Me_{1})
 (Me_{2}) is the inverse machine of Me_{1}
 (Me_{1}) is the inverse machine of Me_{2}.
 All of the above are false.
 Consider the following FAs:
Which of the following is true?
 FA_{1} ⊂ FA_{2}
 FA_{2} ⊂ FA_{1}
 FA_{1} = FA_{2}
 none of the above
 Consider a DFA over ∑ = (a, b) accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?
 8
 14
 15
 48
 What is the number of states in the minimized DFA that accepts all strings whose 7^{th} symbol from Right end is 1
 254
 256
 8
 237
 Which of the following statements is true?
 The union of two equivalence relations is also an equivalence relation.
 Regularity is preserved under the operation of string reversal.
 All subsets of regular sets are regular.
 A minimal DFA that is equivalent to a NFA with n nodes has always 2^{n} states.
 Identify correct statements from the following.
I. A FSM can be designed to add two integers of any arbitrary length (arbitrary number of digits).
II Every subset of a countable set is countable.
 I only
 Neither I nor II
 II only
 I and II
 How many states are there in minimized DFA of the following DFA:
 2
 4
 3
 5
 Consider the sequential machine M given below:
01AC, 0B, 1BF, 1D, 1CD, 0E, 1DC, 0F, 1ED, 1C, 1FC, 1C, 1GC, 1D, 1
Which of the following sequential machines is the standard (i.e. reduced equivalent machine of M)?

01AB, 0C, 1BB, 0D, 1CD, 1B, 1DB, 1B, 1

01AB, 0C, 1BD, 1B, 1DA, 1A, 1ED, 1A, 0

01AB, 0C, 1BB, 0C, 1CC, 1B, 1

01AB, 0C, 1BB, 0C, 1CC, 1B, 1

 One fine day I draw a DFA for a language which I know very well and place in the house. On that night my house was robbed. The robber did the following:
He just removed one of nonstarting states from my DFA, removed all edges associated with it, redrew it on another paper and robbed my original paper. Next day morning I found that my paper was robbed and saw another FA there. From that day I am thinking what language could be accepted by that FA. My original DFA is shown below.
Can you help me in finding out the state to be removed to satisfy the following.
 The finite automata accepts all strings whose last but one symbol is 1.
 The finite automata accepts all strings which end with 11.
 A
 B
 C
 D
Answers
 c
 a
 c
 c
 b
 d
 c
 c
 c
 a
 b
 a
 c
 c
 b
 d
 d
 b
 a
 a
 a
 d
 d
 c
 d
 b
 b
 d
 c
 a
 c
Exercises
 Define a DFA with an example?
 Design a DFA which accepts any number of a’s followed by a string ba followed by a string a’s and b’s?
 What is a transition graph and transition table?
 Obtain a DFA to accept strings of a’s and b’s, except those containing a substring aab?
 Design a DFA to accept strings having
 exactly one a
 at least one ‘a’
 not more than 3a’s
 Obtain a DFA to accept strings of 0’s, 1’s and 2’s, beginning with a 1, followed by odd number of 0’s and ending with a 2?
 Obtain a DFA to accept strings starting with two 0’s and ending with at least two 1’s?
 Obtain a DFA to accept a strings of a’s and b’s with at most two consecutive b’s [abababb]?
 What is a NFA, write the procedure to convert a NFA to a DFA?
 Obtain a DFA to accept the integer numbers represented in binary and is a multiple of 5.
 Obtain a DFA to accept a language L that has strings of a’s and b’s ending with ab.
 Construct a DFA to test whether a binary number is
 Divisible by 6
 Divisible by 7
 Obtain a DFA whose number of a’s is divisible by 7 and number of b’s is divisible by 5?
 Obtain a DFA to strings that begin or end with 0, 1?
 Construct a DFA to accept the strings over z = {a, b} with the property that every block of length of 5 contains at least two a’s?
 Write the differences between DFA and NFA?
 Obtain a DFA to accept a language L that has strings of a’s and b’s ending with ab or ba.
 Convert the following NFA into its equivalent DFA.
 Define epsilonclosure?
 Obtain a DFA to accept a language L that has strings with a’s and b’s such that difference in number of a’s and b’s is multiple of 3.
 Obtain a DFA to accept the language L = {awa w is string with a’s and b’s}
 Convert the given ɛ NFA to its equivalent DFA.
 Define the following terms:
 DFA
 NFA
 ɛNFA
 Construct DFAs that accept the following languages on the alphabet ∑ = {a, b}
 all strings with exactly one a
 all strings with at least one a
 all strings except those which end with abb
 Convert to DFA the following NFA:
01q_{0}q_{1}φ*q_{1}q_{0}q_{1}, q_{2}q_{2}φq_{1}
 Define finite automata. Discuss why we study Automata.
 Design the DFAs for the following languages.
 L = {w/w mod 3 = 0, w is string with a’s and b’s}
 set of all strings (on the alphabet ∑ = {0, 1}) that either begin or end, or begin as well as end with the substring 01
 decimal strings divisible by 3
 Explain the procedure to construct DFA for the given NFA using subset construction scheme.
 Show that every positive integer can be expressed as a product of prime numbers.
 Design a NFA to recognize the following set of the strings:
 abc, abd, aacd
 0101, 101, 011 ∑ = {0, 1}
 Obtain a DFA to accept binary numbers (over the alphabets {0, 1}) that are divisible by 5 and start with 1.
Hint: 101, 1011, 101011 strings should be valid, 0101, 01011 are not valid.

Obtain a DFA to accept a language L = {w/wmod 3 > = wmod 2} where w Σ * and ∑ = {a, b}
Hint: Strings of length 3, 9, 15, 21 are not valid or in general 3 + 6 n/n ≥ 0 are not valid.
 Consider the DFA
01→ABABACCDB*DDAEDFFGEGFGHGD
 Draw the table of distinguishabilities for the DFA
 Construct the minimum stateequivalent DFA.
 Find the language accepted by the following and prove that the FA generates strings where each prefix has at most one more a than b’s and atmost one b more than a’s.
Hint: This can be proved by deducing the properties of the strings, taking the automaton to each of four states and using mathematical induction on the length of the string.

In converting NFA to DFA, the number of states may increase substantially. Give upper and lower bounds on the maximum increase in number of states for an nstate NFA.
Hint: Consider the Theorem 1 in 2.4 and the Example 2.17.