Roll No..............................

MEERUT INSTITUTE OF ENGINEERING AND TECHNOLOGY

NH-58, Delhi-Roorkee Highway, Baghpat Road, Meerut – 250 005 (U.P.)

SOLUTIONS/Class Test – 1 (Even Semester, 2023 – 24)

Course/Branches: B Tech (CSE/CSIT/AI/AIML/CSDS/IOT/IT) Semester: IV

Subject Name: Theory of Automata & Formal Languages Max. Marks: 60
Subject Code: BCS – 402 Time Allowed: 120 Minutes

NOTE: Solutions are deliberately expanded to enhance the understanding of underlying concepts, and pre-
pare you well for other similar questions. Also, there are some important additional details. Read everything
very carefully!

Section – A (CO -1) # Attempt both the questions # 30 Marks

Q 1 Attempt any SIX questions. Each question is of two marks. (2 × 6 = 12 Marks)

(a) Define ε-closure of a state for an ε-NFA . (K1 )

Solution. Let N = Q, Σ, δ , q, F be an ε-NFA, i.e., N is an FA with ε-moves. The ε-closure of a state
q ∈ Q, denoted by Cε (q), is the set of states in Q that are reachable from q by using one or more
ε-moves. We always have q ∈ Cε (q). For the ε-NFA with the state diagram as in Fig. 1, we have




Cε q0 = q0 , q1 , q2 , Cε q1 = q1 , q2 , and Cε q2 = q2 . †

0 1 2

q0 ε q1 ε q2

Figure 1: The state diagram of ε-NFA for Q. 1(a) and Q. 2(c).

(b) Differentiate between a DFA and an NFA. (K1 )

Solution. Let M = Q, Σ, δ , q0 , F be a DFA or an NFA, where the symbols have their usual meanings.
Some major differences between the two types of FAs are as listed in Table 1. †

(c) Use a suitable example to explain finite automaton without output. (K2 )
Solution. A finite automaton M over an alphabet Σ is the simplest model of computation that helps to
recognise patterns of strings w ∈ Σ∗ consisting of a finite number of alphabet symbols. It consists of a

finite set of states Q = q0 , q1 , . . . , qn−1 , where q0 is called the initial state, and a set F ⊆ Q has accept
states. At each step of computation, M reads leftmost symbol of an input string w (say a ∈ Σ), and


switches from a state q ∈ Q to a state p ∈ Q (with possibly p = q). That is, we have p := δ q, a , where
δ : Q × Σ → Q is called the transition function of the automaton M. So, the function δ specifies how
 Table 1: Differences between a DFA and an NFA

DFA NFA
δ (r, a) is defined for all pairs (r, a) ∈ Q × Σ δ (r, a) may not be defined for some pairs (r, a) ∈ Q × Σ
δ (r, a) ∈ Q δ (r, a) ∈ P(Q)
ε-moves are not involved Use of ε-moves is common
is a single machine acts like multiple DFAs computing at the same time
difficult to construct easy to construct
w is accepted if δb(q0 , w) ∈ F w is accepted if δb(q0 , w) ∩ F ̸= ∅
execution time is less; needs more space less space is needed; execution takes longer time
each DFA is an NFA no NFA is a DFA
computation of regex is difficult computation of regex is easier

M switches states in Q after reading w left-to-right (one symbol at a time). Suppose δb(q0 , w) = q ∈ Q.
We say w is recognised by M if q is an accept state, i.e., q ∈ F. Otherwise, we say w is not recognised
by the automaton M. Therefore, the main role that a finite automaton without output plays is that it
acts like an acceptor or a rejector of strings. For example, consider a DFA with the state diagram as
 
in Fig. 2(a). We have Q = q0 , q1 , Σ = {0, 1}, F = q1 , and the transition function δ is given by





δ q0 , 0 = q0 , δ q0 , 1 = q1 , δ q1 , 0 = q0 , and δ q1 , 1 = q1 . Notice that it accepts exactly the bit
strings that end in 1. †

0 1 0,1 0,1
0
0 0,1 0
q0 q1 p q r s
1
(a) DFA for Q. 1(d) (b) NFA for Q. 1( f )

Figure 2

(d) Discuss the Myhill-Nerode theorem. (K2 )

∗ 1
Solution. Let Σ be a finite alphabet, and L ⊆ Σ . The Myhill-Nerode theorem uses the concept of
indistinguishable strings in Σ∗ to give a convenient criterion to verify when L is a regular language. We
say two strings x, y ∈ Σ∗ are indistinguishable with respect to L, denoted by x ≡L y, if we have

xz ∈ L ⇔ y z ∈ L, for every string z ∈ Σ∗ . (1.1)

Equivalently, x and y are distinguishable with respect to L if xz, yz ∈ L, for some string z ∈ Σ∗ . According
to the theorem, a set L ⊆ Σ∗ is a regular language if and only if the equivalence classes of the relation

1 It
is a fundamental fact related to formal language, which was first proven by the British mathematician John Myhill in 1957,
and also independently by the American mathematician Anil Nerode in 1958.

2
 (1.1) gives a finite partition of the set Σ∗ . Consider the set L = x ∈ {0, 1}∗ | x ends with 1 realised


by a DFA with the state diagram as in Fig. 2(a). Notice that a bit string w terminates at q1 if it ends with
1; otherwise, it terminates at the initial state q0 . We may thus take C1 and C2 to be the set of strings that
do and respectively don’t end in 1. In the partition given by C1 and C2 , we have C2 = L so that the states
associated with it are precisely the accept states. †

(e) Use a suitable example to explain an NFA. (K2 )

Solution. For an NFA N = Q, Σ, δ , q0 , F , we may have δ (q, a) = ∅, i.e., transitions may not be defined
for all pairs (q, a) ∈ Q × Σ. We may also have δ (q, a) ⊂ Q, for some pairs (q, a). So, in this case,
δ (q, a) ∈ P(Q), where P(A) denote the power set of a set A. For example, FA shown in Fig. 2(b) is the
state diagram of an NFA. The idea of non-determinism is a theoretical possibility that is useful in solving
more general types of computation problems. †

(f) Write the transition table for FA with the state diagram as in Fig. 2(b). Is it an NFA or a DFA? (K2 )
Solution. The transitions are as given below:





δ p, 0 = p, q , δ p, 1 = p , δ q, 0 = δ q, 1 = r ,





δ r, 0 = s , δ r, 1 = ∅, δ s, 0 = δ s, 1 = s

Therefore, it is an NFA. †

(g) Use a suitable diagram to explain what is an automaton. (K2 )

Solution. The term “automaton” is a Latin translation of the Greek word “automatos" that means self-
acting2 . The term “automata” is a plural of automaton. In general, an automaton M is an abstract model
of computation that performs by moving through a sequence of states and configurations. At every step,
a specified transition function determines the next configuration considering only a finite part of the
current configuration. It accepts an input string when it reaches to an accepting configuration. There are
four mainly types of automata, namely, finite automata, pushdown automata, linear bounded automata,
and the most general and powerful Turing machines. These families of automata are listed in hierarchal
form in order of complexity levels of the associated languages. Through this setup, we understand how
machines compute functions and solve decidable problems (see Fig. 3). †

function(...) {
Input ... Output
}

Figure 3: An automaton as an input-output device.

Q 2 Attempt any THREE questions. Each question is of six marks. (3 × 6 = 18 Marks)

2 It was first used by the eighth century Greek poet and historian Homer to depict the movement of his wheeled tripods.

3
(a) Construct a DFA for each one of the following: (K3 )

(i) the set of strings in {0, 1}∗ ending in 101;

(ii) the set of strings in {0, 1}∗ that starts with 0 and ends with 11;
(iii) the set of strings w ∈ {0, 1}∗ such that |w| mod 3 = 0;
(iv) L = 0m 1n 2 p ∈ {0, 1, 2}∗ | m, n ≥ 0, p ≥ 1 .


Solution. The state diagram of a DFA for (i) is shown in Fig. 4(a); the state diagram of a DFA for (ii) is
shown in Fig. 4(b); the state diagram of a DFA for (iii) is shown in Fig. 4(c); and, the state diagram of
a DFA for (iv) is shown in Fig. 4(d). †

0 1 0 1
1 p q r

1 0 1 0
p q r s 1 1
0 0
0 D 0,1 s 1
0
(a) DFA for Q. 2a(i) (b) DFA for Q. 2a(ii)

0
q1 1 q1 2 0,1,2
0,1 1 2
2 0,1
q0 0,1 q0 qf D
0,1 0 2 2
0
q2 0 q2 q3 1
1
(c) DFA for Q. 2a(iii) (d) DFA for Q. 2a(iv)

Figure 4

(b) Convert NFA with the state diagram as in Fig. 2(b) into an equivalent DFA. (K3 )
Solution. Applying subsets construction method to the transition table of NFA with the state diagram as
in Fig. 2(b), we obtain the transition table of an equivalent DFA, as shown in Fig. 5(a). So, the state
diagram the DFA is as in Fig. 5 (b). †

(c) Convert ε-NFA shown in Fig. 1 into an equivalent DFA. (K3 )




Solution. The ε-closure of states are given by Cε q0 = q0 , q1 , q2 , Cε q1 = q1 , q2 , and Cε q2 =

q2 . It thus follows from the three tables in Fig. 6 that equivalent NFA N has the state diagram as
in Fig. 7(a). Notice that each state turns out to be an accepting state, because we can reach to the
accept state q2 from all other states via an ε-move. We next use subsets construction method to find an
equivalent DFA. This has the state diagram as in Fig. 7(b). †

4
 δ 0 1
1 1
p pq p 1
pq pqr pr 0 0 1
p pq pqr pr
pqr pqrs pr
pr pqs p 0 0
0
pqs pqrs prs
pqrs pqrs prs pqs pqrs prs ps
0 1 1
prs pqs ps
ps pqs ps 01
0 1
(a) Transition-Table for Q. 2b (b) DFA for Q. 2b

Figure 5

PS ε∗ 0 ε∗ PS ε∗ 1 ε∗ PS ε∗ 2 ε∗
q0 q0 q0 q0 , q1 , q2 q0 q0 ∅ ∅ q0 q0 ∅ ∅
q1 ∅ ∅ q1 q1 q1 , q2 q1 ∅ ∅
q2 ∅ ∅ q2 ∅ ∅ q2 q2 q2
q1 q1 ∅ ∅ q1 q1 q1 q1 , q2 q1 q1 ∅ ∅
q2 ∅ ∅ q2 ∅ ∅ q2 q2 q2
q2 q2 ∅ ∅ q2 q2 ∅ ∅ q2 q2 q2 q2

(a) (b) (c)

Figure 6: Tables for Q. 2c.

q0 0 q012 1 q12
0 1 2 1
0
0, 1 1, 2 2 2 2 0
q0 q1 q2

2 q2 DS
0, 1, 2 0,1
(a) (a)

Figure 7: The state diagrams of NFA and DFA for Q. 2(c).

  
(d) Consider the DFA M = Q, Σ, δ , q0 , F , where Q = q0 , q1 , . . . , q6 , q7 , Σ = a, b , F = q3 , and

5
 the transition function δ of M is given by





δ q0 , a = q1 , δ q0 , b = q0 , δ q1 , a = q0 , δ q1 , b = q2 ,





δ q2 , a = q3 , δ q2 , b = q1 , δ q3 , a = q3 , δ q3 , b = q0 ,





δ q4 , a = q3 , δ q4 , b = q5 , δ q5 , a = q6 , δ q5 , b = q4 ,





δ q6 , a = q5 , δ q6 , b = q6 , δ q7 , a = q6 , δ q7 , b = q3 ,

Construct the minimum state automaton equivalent to the DFA M. (K3 )

Solution. The state diagram of M is as in Fig. 8(a). Since the states q4 , q5 , q6 , q7 are unreachable, we can
remove them straight away. For the rest of it, we have
 
0 − equivalences : q0 , q1 , q2 , q3 ;
  
1 − equivalences : q0 , q1 , q2 , q3 ;
   
2 − equivalences : q0 , q1 , q2 , q3

It thus follows that automaton with the state diagram as in Fig. 8(b) is the desired equivalent DFA. †

b b a

q0 a q1 b q2 a q3 a
b q0 q1
a b b
a b a
b b b
q4 b q5 a q6 a q7
q3 a q2
a
b a
(a) State diagram for Q. 2d (d) Minimal DFA for Q. 2d

Figure 8

(e) Convert the Mealy machine shown in Fig. 9(a) into an equivalent Moore machine. (K2 )

Solution. An equivalent Moore machine is shown in Fig. 9(b). †

Section – B (CO -2) # Attempt both the questions # 30 Marks

Q 3 Attempt any SIX questions. Each question is of two marks. (2 × 6 = 12 Marks)

(a) Explain the operators of regexes. (K1 )

Solution. For two regexes R1 and R2 , the three commonly used operators are given by (i) the sum R1 +R2 ;
(ii) the concatenation R1 R2 ; and, (iii) the Kleene closure R∗1 . If L1 and L2 are respectively the regular
languages represented by R1 and R2 , then we have L1 ∪ L2 is represented by the regex R1 + R2 , L1 L2 is
represented by the regex R1 R2 , and L1∗ is represented by the regex R∗1 . †

6
 0/z1 0 0
q1 q2 0/z2 q1 / q2 /z1 q′2 /z2 0

1
1/z1 0/z1 1/z1 1 0 1
0
1
q3 1/z2 q3 /z1 q′3 /z2 1

(a) Mealy Machine for Q. 2(e) (b) Moore Machine for Q. 2(e)

Figure 9

(b) Write a regex over the alphabet Σ = {a, b, c} containing at least one a and two b’s. (K2 )
Solution. It is given by (a + b + c)∗ a(a + b + c)∗ b(a + b + c)∗ b(a + b + c)∗ . †

(c) Explain and prove the Arden’s theorem. (K2 )

Solution. Arden’s theorem states that, for any two regular expressions P and Q over an alphabet Σ with
P ̸= ε, the recurrence relation R = Q + RP has a unique solution given by R = QP∗ . For a proof, we have
 
R = Q + RP = Q + Q + RP P
= Q + QP + RP2 = · · ·
= Q + QP + QP2 + QP3 + · · ·
= Q ε + P + P2 + P3 + · · ·
 

= QP∗

So, QP∗ is a unique solution of the recurrence relation R = Q + RP. †

Arden’s theorem provides an elegant method to write a regular expression for a finite automaton. More
precisely, suppose M is finite automaton with n states q1 , q2 , . . . , qn such that q1 is the initial state. We
repeatedly apply Arden’s theorem to solve the following linear systems of state equations:

q1 = q1 a11 + q2 a21 + · · · + qn an1 + ε;

q2 = q1 a12 + q2 a22 + · · · + qn an2 ;
..
.
qn = q1 a1n + q2 a2n + · · · + qn ann ,

where ai j ∈ Σ are labels of the edges from state qi to state q j . Further, we take ai j = ∅ when no such
edge exists. The goal is to obtain the regular expressions for all available accept states. The final answer
is obtained by taling sum of these expressions. The theorem finds applications in compiler design: During
lexical analysis, regular expressions are used to define tokens of a program. By simplifying and converting
them into equivalent finite automata, a compiler efficiently recognises and tokenises input streams.

(d) Express the regex (aaa)∗ (bbb)∗ b in words. (K2 )

Solution. This regex represents the language consisting of strings over the alphabet {a, b} having zero

7
 or more occurrences of the triplet “aaa”, followed by zero or more occurrences of the triplet “bbb”, and
ending in the symbol b. †

(e) Find regex for the language consisting of strings in {0, 1}∗ such that the 10th symbol from the right
ends in 0. (K2 )
∗ 9
Solution. It is given by (0 + 1) 0(0 + 1) . †

(f) Compare the terms regular expression, regular set, and a finite automaton. (K2 )
Solution. A regular expression over an alphabet Σ is a “pattern form” constructed using symbols in Σ and
usual operations such as sum, concatenation, and the ∗-closure. A regular expression R for a regular set
(or regular language) L provides an algebraic description of the finite automaton M realising L. In some
cases, it provides the only way to represent a finite automaton, especially when the latter has very large
number of minimum states. Kleene proposed the concept of regular expressions to capture the “structure
of strings" in a regular language L by matching their patterns. The concept of regular expression is an
efficient tool to search and process strings of a regular set. †

(g) Given a regular expression R, design a finite automaton for R∗ . (K2 )

Solution. Suppose the language described by regular expression R has finite automaton with the state dia-
gram as in Fig. 10(a). Then a finite automaton for R∗ has the state diagram as in Fig. 10(b). In this, ε-move
from q f to q0 creates the loop (ba)∗ , and the ε-move from q′0 to q′f ensures that the associated regular set
contains ε. †

ε
ε
b a ε b a ε
q0 q1 qf q′0 q0 q1 qf q′f

(a) FA for R (b) FA for R∗

Figure 10: The FAs for Q. 3(g).

1
q0 0 q1 0 0, 1 0 1
0
0 1 1 0 1

1 q2 −1

(a) FA for Q. 4(a) (b) FA for Q. 4(e)

Figure 11

8
Q 4 Attempt any THREE questions. Each question is of six marks. (3 × 6 = 18 Marks)

(a) Use Arden’s theorem to construct a regex for FA with the state diagram as in Fig. 11(a). (K3 )
Solution. In this case, the “state equations" are given by

q0 = ε + q2 · 0; (1.2a)
q1 = q0 · 0 + q1 · 0; (1.2b)
q2 = q0 · 1 + q1 · 1 + q2 · 1; (1.2c)

Applying Arden’s theorem to (1.2b), we obtain

q1 = q0 · 00∗ = q0 · 0+ .

Substituting this in (1.2c), we have

q2 = q0 · 1 + q1 · 1 + q2 · 1
= q0 · 1 + q0 · 0+ 1 + q2 · 1
= q0 1 + 0+ 1 + q2 · 1

Once again, applying Arden’s theorem to the last equation, it follows that

q2 = q0 1 + 0+ 1 1∗ .

We can thus write (1.2a) as

q0 = ε + q2 · 0 = ε + q0 1 + 0+ 1 1∗ 0

Therefore, applying Arden’s theorem one last time, we obtain

∗
1 + 0+ 1 1∗ 0 .

q0 = ε ·

Since q0 and q1 are accept states, the associated regular expression is given by

∗ 
1 + 0+ 1 1∗ 0 ε + 0+
 

This completes the solution. †

(b) Convert regex 10 + (00 + 11)0∗ 10 to an equivalent FA. (K3 )

Solution. In this case, we start with a finite automaton as in Fig. 12(a) having only the initial state q0 and
an accept state q f . The top edge for the part 10 and the bottom edge for the part (00 + 11)0∗ 10. Using
two more states q1 and q3 , the top part of modified finite automaton as in Fig. 12(b) accepts 1 followed
by 0; and, the bottom part is modified to accept (00 + 11), followed by a 0-loop at q3 , and then 10.
With two additional states q2 and q4 , we obtain the finite automaton as in Fig. 12(c), using similar idea.
Finally, using the state q5 , we obtain a finite automaton for the regular expression 10 + (00 + 11)0∗ 10,
as shown in Fig. 12(d). †

9
 q1

10 1 0
q0 0 qf
q0 qf
00 + 11 10
q3
(00 + 11)0∗ 10
(a) (b)

q1 q1
0
1 0 1 qf
q0 1 q2 qf q0 1 q2
0 0
0
0 1 10 0 1
q4 0 q3 q4 0 q3 1 q5

(c) (d)

Figure 12: The FAs for Q. 4(b).

(c) Find regexes of the two regular sets given below: (K3 )

(i) L = w ∈ {a, b}∗ | na (w) mod 5 = 0 ;



(ii) L = w ∈ {a, b}∗ | w contains exactly three a’s .



∗
Solution. A regex for (i) and (ii) are respectively given by b∗ ab∗ ab∗ ab∗ ab∗ ab∗ and b∗ ab∗ ab∗ ab∗ . †

(d) State Kleene’s theorem and illustrate its proof using suitable examples. (K2 )
∗
Solution. The Kleene’s theorem states that a set L ⊆ Σ is a regular language if and only if some regular
expression R over the alphabet Σ describes L. Since we know that L is a regular language if and only
if there is a finite automaton M such that L = L(M). The theorem boils down to equivalence between
a regular expression and a finite automaton. Using the recursive definition of regular expression, a
simple structural induction establishes the fact that there is a finite automaton for every type of a regular
expression. In the solution of Q. 4(b), however, we have used a more direct approach. The proof of the
converse is bit involved. However, given a finite automaton, one may use state elimination method to
obtain its regular expression. We first list the general rules (to be followed in that order only):

(1) If there is an incoming edge at the initial state q0 , introduce a new initial state q′0 , and add an ε-edge
from q′0 to q0 .
(2) If there is an outgoing edge from a final state q f , introduce a new final state q′f , and add an ε-edge
from q f to q′f .
(3) Replace all final states by a single final state, using ε-edges.

10
(4) Eliminate all states one-by-one (in any order), excepting the initial and the final state.

We now consider a DFA realising the strings w ∈ {0, 1}∗ such that n1 (w) mod 3 = 0. The related state
diagram is shown in Fig. 13(a). Since there is an incoming edge at q0 , by Rule-(1), we introduce q′0 as
the new initial state, and add an ε-move from q′0 to q0 . The modified state diagram is as in Fig. 13(b).
Again, since there is an outgoing edge from the final state q0 , by Rule-(2), we introduce a final state q f
and add an ε-move from q0 to q f . The resulting state diagram is as in Fig. 13(c). The Rule-(3) is not
applicable in this case. To apply the Rule-(4), we start with elimination of the state q2 . In doing so, all
edges through q2 are to be accounted for. We thus obtain a DFA with the state diagram as in Fig. 13(d).
We next eliminate the state q1 so that the resulting DFA has the state diagram as in Fig. 13(e). Finally, it
follows from Fig. 13( f ) that associated regular expression is 0 + 10∗ 10∗ 1. †

0 0 0 0 0 0

1 1 ε 1 1
q0 q1 q2 q′0 q0 q1 q2

1 1
(a) (b)

0 0 0 0 0

ε 1 1 ε 1
q′0 q0 q1 q2 q′0 q0 q1

10∗ 1
ε 1 ε

qf qf

(c) (d)

ε ε
q′0 q0 10∗ 10∗ 1 q′0 q0 0 + 10∗ 10∗ 1

ε ε

qf qf

(e) (f)

Figure 13: The state diagrams of FAs for Q. 4(d).

(e) Write regular expression for the following two regular sets: (K3 )

(i) consisting of strings w ∈ {0, 1}∗ with the same number of 0;s and 1’s such that, in every prefix of w,

11
 the number of 0’s and 1’s differ by at most 1;
(ii) consisting of strings w ∈ {0, 1}∗ that don’t contain 101 as a substring.

Solution. For (i), the regular set contains strings w ∈ {0, 1}∗ that alternate between 0’s and 1’s. Said differ-
ently, it contains precisely the string w ∈ {0, 1}∗ such that the absolute difference in the count of 0’s and 1’s
in every prefix of w is less than 2. This latter version help us to think in terms of a NFA for the given regular
set. For, the minimal NFA must have 3 states respectively representing the differences of −1, 0, and 1. Start
in state 0 and go to state 1 when reading a 1; and, to the state −1, when reading a 0. In state 1, go back
to state 0 when reading a 0, or else fail when reading another 1. We can use symmetry to process similarly
while in state −1. We now read a regular expression for this NFA with the state diagram as in Fig. 11(b).
Based on the preceding discussion, if you read 01 or 10, the net difference is zero. If not stopped, then read
one more 0 or 1. Therefore, the regular expression is obtained as (01 + 10)∗ (ε + 0 + 1). For (ii), notice that
we are looking for a regular expression of a DFA that is complement of a DFA with the state diagram shown
in Fig. 14(a). Therefore, for (ii), a regular expression is given by
∗
(0 + 1)∗ (0 + 00)∗ (1 + 11)(0 + 00)∗ 0∗ 11∗ 000∗ 11∗ 01(0 + 1)∗ ,


as obtained from the diagram shown in Fig. 14(b). †

0 1 0,1 0 1 0,1

q1 1 q2 0 q3 1 q4 q1 1 q2 0 q3 1 q4

0 0
(a) (b)

Figure 14

12