Question Bank

Name of Subject: Theory of Subject Class : T.E

Computation Code: (I.T.)
Academic Year: 2025- Semester:
26 First

UNIT 1- FINITE STATE MACHINES

1. Define the following terms with suitable example of each:
a. Symbol
b. Alphabet
c. String or Word
d. Proper prefix of a string
e. Suffix of a string
2. Define and explain with suitable example:
a. Natural Language
b. Formal Language
3. What is the basic machine? Enlist the important features of basic machine.
4. State and define Finite State Machine(FSM).
5. How are FSMs represented?
6. Define string acceptance and rejection by FSM.
7. What are the properties and limitations of Finite State Machine?
8. Define NFA and DFA in the tuple format.
9. What is the basic difference between NFA and DFA?
10. Give formal definitions of NFA with ε-moves and ε-closure.
11. Prove that two FA’s are identical. Write the expressions for the same.
12. Enlist the applications and limitations of FA.
13. How is FSM different from NFA and DFA.
14. Design a FSM
 Question Bank

Name of Subject: Theory of Subject Class : T.E

Computation Code: (I.T.)
Academic Year: 2025- Semester:
26 i) for divisibility by 3 tester of a binaryFirst
number.
ii) for divisibility by 5 tester of a decimal number.
iii) for divisibility tester of unary number by 2.
15. Design a FSM to accept those strings having 101 or 110 as a substring over ∑ = {0,1}.
16. Design FA which accepts only those strings which ‘starts with 1’ and ‘ends with 0’ over ∑ =
{0,1}.
17. Design FA which accepts only those strings which always ends with “aa” over ∑ = {a,b}.
18. Design an FA over ∑ = {0,1} for the following
i) Strings which end in either “00” or “11”.
ii) Strings which contain either “01” or “110”.
iii) Strings with even number of 0’s and odd number of 1’s.
iv) Strings with even number of 0’s and even number of 1’s
19. Design a FA that reads strings defined over ∑ = {a,b} and accept only those strings
which ends up in either “aa” or “bb”.
20. Construct a FSM that reads strings made up of letters in word “CHARIOT” and
recognize those string that contain “CAT” as a substring.
21. Construct a NFA that accepts the set of all strings over {a, b} ending in aba.
22. Construct NFA which accepts the strings containing either ‘01’ or ‘10’ over the alphabet
{0,1}.
23. Construct NFA in which double ‘1’ is followed by double ‘0’ over the alphabet {0,1}.
24. Design a DFA which accepts the odd number of 1’s and any number of 0’s over {0,1}.
25. Construct DFA accepting following language over {0,1}
i) Set of all strings ending with 00
ii) Set of all strings such that 3rd symbol from right end is 1.
26. Design a DFA for accepting all those strings over {0,1} which is not containing 101 as
a substring.
 Question Bank

Name of Subject: Theory of Subject Class : T.E

Computation Code: (I.T.)
Academic Year: 2025- Semester:
26 27. Consider the following NFA with ε – moves :First
ε a B c
p Φ {p} {q} {r}
q {p} {q} {r} Φ

r {q} {r} Φ {p}

i. Compute the ε – closure of each state.

ii. Give all the strings of length three or less accepted by the automaton.
iii. Convert the automaton to its equivalent DFA.

28. Construct DFA equivalent to NFA M= ({p, q, r, s}, {0, 1}, δ, p, {q, s} )
Where, 0 1
p {q, {q}
δ= q {r}s} {q, r}
r {s} {p}
s Φ {P}
*
29. Construct DFA equivalent to NFA M= ({p, q, r, s}, {0, 1}, δ, p, {s} )
Where, 0 1
p {p, {p}
δ= q {r q} } {r}
r {s} Φ
s {s} {s}
*
30. Show stepwise process of constructing DFA equivalent to the following NFA:

31. Construct NFA for the following regular expressions:

i) 0*1*2*
 Question Bank

Name of Subject: Theory of Subject Class : T.E

Computation Code: (I.T.)
Academic Year: 2025- Semester:
26 First
ii) (00 + 1 )* (10)*

32.Convert the following NFA with Є- moves to its equivalent NFA without Є-moves.

33. Design a DFA for following language:

L = { w | w is Binary word of length 4i ( where I >= 1) such that each consecutive
block of 4 bits contains atleast 2 0’s }.
= {0000, 0110, 01101100,…………………..}
34. Convert the following NFA into equivalent DFA
M = ({q0, q1}, { 0, 1} , δ , q0 , { q1})
where δ is :
δ(q0 ,0) = {q0, q1} , δ(q0 ,1) = {q1},
δ(q1 ,0) = Φ , δ(q1 ,1) = {q0, q1}

35. Convert the following NFA to its equivalent DFA

36. Convert the following with Є moves to its equivalent DFA

37. Construct the NFA for the language of all strings that begin and end with same symbol over
the alphabet ∑ = { 0, 1}.
38. Define Moore and Mealy machines in tuple format?
39. Compare Moore and Mealy machines with suitable example.
 Question Bank

Name of Subject: Theory of Subject Class : T.E

Computation Code: (I.T.)
Academic Year: 2025- Semester:
26 First
40. Design a Moore machine which will recognize the language of all words of the form
(a + b)* aa (a + b)*. Let the machine display “A” for acceptance and “R” for rejection of
words.
41. Design a Moore machine for checking divisibility by 3 of a given binary number(residue of
3).
42. Design a Moore machine to generate 1’s complement of the given binary number.
43. Design a Moore machine to generate 2’s complement of the given binary number.
44. Design a Mealy machine to generate 2’s complement of the given binary number.
45. Design a Moore and Mealy machine for binary input sequence such that if it has
a substring 110 the machine outputs A, if it has a substring 101 machine outputs
B, otherwise it outputs C.
46. the alphabet ∑ = { 0, 1}.
47. Design Moore and Mealy machine to convert substring 121 to 212 for strings of language
having input from {0,1,2}.
48.Design a Moore machine which counts the occurrence of substring aab in a long i/p
string over {a,b}.
49.Construct Moore and Mealy machine to print no of vowels and consonants for a string of
alphabets.

50. Design Mealy machine which accepts strings containing ‘cat’ and ‘rat’.

51. Consider the following Mealy machine , construct a Moore machine equivalent to It.
 Question Bank

Name of Subject: Theory of Subject Class : T.E

Computation Code: (I.T.)
Academic Year: 2025- Semester:
26 52. Find out whether M1 and M2 are equivalentFirst
a)

b)

53.Convert the following Moore machine to its equivalent Mealy machine.

Input
Stat Outpu
A B
e t
q q q 1
q0 q1 q3 0
q1 q3 q1 0
q2 q0 q3 1
54.Convert the following Moore machine to3 its equivalent
3 2 Mealy machine

Input
Stat Outpu
e 0 1 t
p s Q 0
q q R 1
r r S 0
s s P 0
 Question Bank

Name of Subject: Theory of Subject Class : T.E

Computation Code: (I.T.)
Academic Year: 2025- Semester:
26 First

55.Convert the following Mealy machine to its equivalent Moore machine.

Prese Next
nt Input = 0 State Input = 1
Stat Stat Outpu State Output
q eq t 1 q 0
q1 q1 1 q2 1
q2 q4 1 q4 1
q3 q2 0 q3 1
4 3 1

56. State TRUE or False?

i) Moore machine can have arbitrary number of final states.

ii) Moore machine can have arbitrary number of initial states.

57.Convert the following Mealy machine to its equivalent Moore machine.

0/A 1/B 0/B

Start q1 1/A q2

58.Consider the following Moore machine , convert it to its equivalent Mealy machine.

a b b
Start q1/1
q0/0
a