Finite-Automata
Question 1 |
Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x1 x2 ... xn ∈ Σn, n ≥ 0. Let π(x) = x1 º x2 º ... º xn.
Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of states in any DFA accepting L is ______.
120 | |
136 | |
125 | |
132 |
Question 2 |
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
k ≥ 2n | |
k ≥ n | |
k ≤ n2 | |
k ≤ 2n
|
In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2n states.
Hence k ≤ 2n is necessarily true.
Question 3 |
L0 = {ε}
Li = Li-1∙L for all i>0
The order of a language L is defined as the smallest k such that Lk = Lk+1.
Consider the language L1 (over alphabet 0) accepted by the following automaton.
The order of L1 is ______.
2 | |
3 | |
4 | |
5 |
Now L10 = ϵ and L11 = ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L1
Now L12 = L11 .
L1 = L1 .
L1 = (ϵ + 0 (00)*) (ϵ + 0 (00)*)
= (ϵ + 0 (00)* + 0(00)* + 0(00)*0(00)*)
= (ϵ + 0 (00)* + 0(00)*0(00)* ) = 0*
As it will contain epsilon + odd number of zero + even number of zero, hence it is 0*
Now L13 = L12 .
L1 = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L12 = L13
Or L12 = L12+1 ,
hence the smallest k value is 2.
Question 4 |
Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finite-state automation (DFA) accepting L is _________.
4 | |
5 | |
6 | |
7 |

After converting the NFA into DFA:

After converting the NFA into DFA:

Question 5 |
Identify the language generated by the following grammar, where S is the start variable.
S → XY
X → aX|a
Y → aYb|ϵ
{am bn │ m ≥ n, n > 0} | |
{am bn │ m ≥ n, n ≥ 0} | |
{am bn │ m > n, n ≥ 0} | |
{am bn │ m > n, n > 0} |
So the production S→XY can generate any number of a’s (≥1) in the beginning (due to X) and then Y will generate equal number of a’s and b’s.
So, the number of a’s will always be greater than number of b’s and number of b’s must be greater than or equal to 0 (as Y → ϵ, so number of b’s can be zero also).
Hence the language is {am bn│m>n,n≥0}.
Question 6 |
What is the complement of the language accepted by the NFA shown below?
Assume Σ={a} and ε is the empty string.

∅ | |
{ε} | |
a* | |
{a ,ε} |
Hence the complement of language is: {a* − a+} = {ϵ}
Question 7 |
Definition of a language L with alphabet {a} is given as following.
L = {ank| k>0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
k+1 | |
n+1 | |
2n+1 | |
2k+1 |
So lets check of n = 2,
L = a2k, k>0
Since k>0 than zero.
So L is the language accepting even no. of a's except 'ε'.
So DFA will be,
So, no. of states required is 2+1 = 3.
So for ank, (n+1) states will be required.
Question 8 |
A deterministic finite automation (DFA) D with alphabet Σ={a,b} is given below.
Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
![]() | |
![]() | |
![]() | |
![]() |
(B) False, as it accepts string 'b', which is not accepted by original DFA.
(C) Same reason as (B).
(D) False, as it accepts string 'bba' which is not accepted by the given DFA.
Question 9 |
Consider the finite automaton in the following figure.
What is the set of reachable states for the input string 0011?
{q0, q1, q2} | |
{q0, q1} | |
{q0, q1, q2, q3} | |
{q3} |
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2
Hence δ (q0, 0011) = {q0, q1, q2}
Question 10 |
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.
The missing arcs in the DFA are
![]() | |
![]() | |
![]() | |
![]() |
From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.
Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.
Question 11 |
Let w be any string of length n is {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
n-1 | |
n | |
n+1 | |
2n-1 |

Since L is set of all substrings of “w” (Substring of a string is obtained by deleting any prefix or any suffix from string), so if we consider “w” as “101” , then the substrings of w are { ϵ, 0, 1, 10, 01, 101}.
Since the string “101” is also its substring, so we require 4 states (i.e. for n length string, n+1 states are required) and the NFA would be:
Question 12 |
Given the following state table of an FSM with two states A and B, one input and one output:

If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?
3 | |
4 | |
5 | |
6 |
From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” {highlighted in RED color},
{state 00, 1} -> state “01” , output 0,
{state 01, 0} -> state “10” , output 0,
{state 10, 1} -> state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.
Question 13 |
The above DFA accepts the set of all strings over {0,1} that

begin either with 0 or 1 | |
end with 0
| |
end with 00 | |
contain the substring 00 |
Question 14 |
A minimum state deterministic finite automaton accepting the language L = {w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
15 states | |
11 states | |
10 states | |
9 states |
Question 15 |
Consider the following Finite State Automaton.
The language accepted by this automaton is given by the regular expression
b*ab*ab*ab* | |
(a+b)* | |
b*a(a+b)* | |
b*ab*ab* |
Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.
Question 16 |
Consider the following Finite State Automaton.
The minimum state automaton equivalent to the above FSA has the following number of states
1 | |
2 | |
3 | |
4 |

Question 17 |
Given below are two finite state automata (→ indicates the start state and F indicates a final state)

Which of the following represents the product automaton Z×Y?
![]() | |
![]() | |
![]() | |
![]() |
Lets rename table Z (for sake of clarity)
And Table Y (same as given in question)
The product automata will have states { One1, One2, Two1, Two2} Where One1 is P , Two2 is R and One2 is Q and Two1 is S.
The transition table for Z × Y is given below:
NOTE: LAST TWO ROWS DOESN’T MATCH WITH OPTION A. BUT IF THE ASSUMPTION IN QUESTION SUCH AS STATE “11” IS P AND STATE “22” IS R, HOLDS, THEN THE ONLY OPTION MATCHES WITH PRODUCT AUTOMATA IS OPTION A, AS (FIRST ROW) , P (ON “a”) -> S AND P (ON “b”) -> R, IS THE ONLY OPTION MATCHING WITH OPTION A.
Question 18 |
Match the following NFAs with the regular expressions they correspond to
- 1. ϵ + 0(01*1 + 00) * 01*
2. ϵ + 0(10 *1 + 00) * 0
3. ϵ + 0(10 *1 + 10) *1
4. ϵ + 0(10 *1 + 10) *10 *
P-2, Q-1, R-3, S-4
| |
P-1, Q-3, R-2, S-4 | |
P-1, Q-2, R-3, S-4 | |
P-3, Q-2, R-1, S-4 |
Similarly, The NFA represented by Q, has the form of -> ϵ + 0X*0, where X is regular expression (10*1 + 00) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of -> ϵ + 0X*1, where X is regular expression (10*1 + 01) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0”, so we conclude that it must accept the string of the form of -> ϵ + 0X* 10*, where X is regular expression (10*1 + 10) {resolving the loop at middle state}. It matches with statement 4.
Question 19 |
Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:
3 | |
5 | |
8 | |
9 |
i.e. it generates any string which can be obtained by repetition of three and five 1’s (means length 3, 6, 8, 9, 10, 11, …}
The DFA for the L = (111 + 11111)* is given below.
Question 20 |
Consider the machine M:
The language recognized by M is:
{w ∈ {a, b}* | every a in w is followed by exactly two b's} | |
{w ∈ {a, b}*| every a in w is followed by at least two b’} | |
{w ∈ {a, b}*| w contains the substring 'abb'} | |
{w ∈ {a, b}*| w does not contain 'aa' as a substring} |
Ex: abbbb, abbb...
Option B: It is True. If a string is to be accepted by given machine then it have atleast two b's.
Option C: It is false. Ex: abba. It contains 'abb' as a substring but not accepted by given machine.
Option D: It is false. Ex: abbab. It is not accepted by TM. It doesn't have 'aa' as a substring but not accepting.
Question 21 |
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.
Which one of the following is TRUE?
It computes 1's complement of the input number | |
It computes 2's complement of the input number | |
It increments the input number | |
It decrements the input number
|
Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111
---------------------------
1000 = I/p
----------------------------
It results 2's complement.
Question 22 |
Consider the following deterministic finite state automaton M.
Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is
1 | |
5 | |
7 | |
8 |

There are possible: 7 strings.
Question 23 |
Consider the NFA M shown below.
Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
L1 = {0,1}* - L | |
L1 = {0,1}* | |
L1 ⊆ L | |
L1 = L |

As in above NFA language,
L1 is {0,1}*.












