## Finite-Automata

 Question 1
Consider the following language.
L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.
 A 6
Theory-of-Computation       Finite-Automata       GATE 2020
Question 1 Explanation:

 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?

 A k ≥ 2n B k ≥ n C k ≤ n2 D k ≤ 2n
Theory-of-Computation       Finite-Automata       Gate 2018
Question 2 Explanation:
The number of states in DFA is always less than equal to 2no. of states in NFA.
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
Given a language L, define Li as follows:
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 ______.

 A 2 B 3 C 4 D 5
Theory-of-Computation       Finite-Automata       Gate 2018
Question 3 Explanation:
The regular expression for L1 : ϵ + 0 (00)*
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 _________.

 A 4 B 5 C 6 D 7
Theory-of-Computation       Finite-Automata       Gate 2017 set-01
Question 4 Explanation:
The NFA for regular expression: (a+b)*b(a+b)

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|ϵ
```

 A {am bn │ m ≥ n, n > 0} B {am bn │ m ≥ n, n ≥ 0} C {am bn │ m > n, n ≥ 0} D {am bn │ m > n, n > 0}
Theory-of-Computation       Finite-Automata       GATE 2017(set-02)
Question 5 Explanation:
The production X→ aX | a can generate any number of a’s ≥ 1 and the production Y→ aYb | ϵ will generate equal number of a’s and b’s.
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
Consider the finite automaton in the following figure. What is the set of reachable states fot the input string 0011?
 A {q0,q1,q2 } B {q0,q1 } C {q0,q1,q2,q3 } D {q3 }
Theory-of-Computation       Finite-Automata       GATE 2014(Set-01)
Question 6 Explanation:
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0
{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 7
What is the complement of the language accepted by the NFA shown below?
 A ∅ B {ε} C a* D {a ,ε}
Theory-of-Computation       Finite-Automata       Gate 2012
Question 7 Explanation:
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+}
Hence the complement of language is: {a* − a+} = {ϵ}
 Question 8
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
 A B C D
Theory-of-Computation       Finite-Automata       Gate 2012
Question 8 Explanation:
All states are final states except “q” which is trap state. The strings in language are such that every substring of 3 symbol has at most two zeros. It means that we cannot have 3 consecutive zeros anywhere in string. In the given DFA total four transition is missing, so we have to create the missing transition keeping the criteria in mind that “three consecutive zeros” will lead to trap state “q” as after 3 consecutive zeros whatever comes after that in the string, the string is going to be rejected by DFA.
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 9
Definition of a language L with alphabet {a} is given as foloowing. What is the minimum number of states needed in a DFA to recognize L?
 A k+1 B n+1 C 2n+1 D 2k+1
Theory-of-Computation       Finite-Automata       Gate 2011
Question 9 Explanation:
Given that n is a constant.
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 10
A deterministic finite automation (DFA) D with alphabet Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
 A B C D
Theory of Computation        Finite-Automata       Gate 2011
Question 10 Explanation:
(A) True.
(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 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?
 A n-1 B n C n+1 D 2n-1
Theory-of-Computation       Finite-Automata       2010
Question 11 Explanation:
In order to accept any string of length “n” with alphabet {0,1}, we require an NFA with “n+1” states. For example, consider a strings of length “3” such as “101”, the NFA with 4 states is given below:

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?
 A 3 B 4 C 5 D 6
Theory-of-Computation       Finite-Automata       2009
Question 12 Explanation:
Consider the below given FSM (represented as graph)

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
 A begin either with 0 or 1 B end with 0 C end with 00 D contain the substring 00
Theory-of-Computation       Finite-Automata       2009
Question 13 Explanation:
Option A is false, as the DFA is not accepting the string “10”, option B is false as the DFA is not accepting the string “10” . Option D is false as the DFA doesn’t accept the string “1001” which has “00” as substring. Hence option C , every strings end with “00” is correct.
 Question 14
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?
 A B C D
Theory-of-Computation       Finite-Automata       Gate-2008
Question 14 Explanation:
The product automata will have states {11, 12, 21, 22} and “11” is inItial state and “22” is final state. By comparison we can easily infer that state {11, 12, 21, 22} is renamed as {P, Q, S, R}, wheresP is initial state (state “11”) and R is final state (state “22”).
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 15
Match the following NFAs with the regular expressions they correspond to .      1.e + 0 (01 * 1 + 00) * 01 *
1. e+ 0 (10 * 1 + 00) * 0
2. e+ 0 (10 * 1 + 10) * 1
3. e+ 0 (10 * 1 + 10) * 10 *
 A P-2, Q-1, R-3, S-4 B P-1, Q-3, R-2, S-4 C P-1, Q-2, R-3, S-4 D P-3, Q-2, R-1, S-4
Theory-of-Computation       Finite-Automata       Gate-2008
Question 15 Explanation:
The NFA represented by P, accepts string “00” and then at final state (other than initial state) we have self loop of “1” , so we conclude that it must accept the string of the form of -> ϵ + 0 X* 01*, where X is regular expression (01*1 + 00 ) {resolving the loop at middle state}. It matches with statement 1.
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 16
Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
 A m ≤ 2n B n ≤ m C M has one accept state D m = 2n
Theory-of-Computation       Finite-Automata       Gate 2008-IT
Question 16 Explanation:
Set of states of NFA = n
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
 Question 17
If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?
 A Set of all strings that do not end with ab B Set of all strings that begin with either an a or a b C Set of all strings that do not contain the substring ab D The set described by the regular expression b*aa*(ba)*b*
Theory-of-Computation       Finite-Automata       Gate 2008-IT
Question 17 Explanation:

Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepetd by RE and it belongs to b*aa*(ba)*b*.
 Question 18
Consider the following two finite automata. M1 accepts L1 and M2 accepts L2. Which one of the following is TRUE?
 A L1 = L2 B L1 ⊂ L2 C L1 ∩ L2‘ = ∅ D L1 ∪ L2 ≠ L1 E A and C
Theory-of-Computation       Finite-Automata       Gate 2008-IT
Question 18 Explanation:
In this L1 = (0+10)* 11(0+1)*
L2 = (0=1)* 11(0+1)*
Both L1 and L2 are equal.
Option A is correct.
→ L1 ∩ L2‘ = L1 ∩ L1‘ = ∅ (option C also correct)
 Question 19
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
 A 15 states B 11 states C 10 states D 9 states
Theory-of-Computation       Finite-Automata       Gate-2007
Question 19 Explanation:
Given that number of 0’s and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15. As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required) , so product automata will require (3 × 5=15 states).
 Question 20

 A b*ab*ab*ab* B (a+b)* C b*a(a+b)* D b*ab*ab*
Theory-of-Computation       Finite-Automata       Gate-2007
Question 20 Explanation:
State q3 is unreachable and state q1 and q2 are equivalent, so we can merge q1 and q2 as one state. The resulting DFA will be:

Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.
 Question 21
Consider the following Finite State Automaton.

The language accepted by this automaton is given by the regular expression
 A 1 B 2 C 3 D 4
Theory-of-Computation       Finite-Automata       Gate-2007
Question 21 Explanation:
The minimum state automaton for problem 74 is:
 Question 22
Consider the following DFA in which s0 is the start state and s1, s3 are the final states. What language does this DFA recognize ?
 A All strings of x and y B All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y C All strings of x and y which have equal number of x and y D All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y
Theory-of-Computation       Finite-Automata       Gate 2007-IT
Question 22 Explanation:
Just simulate the running of the DFA on all options - A, B and C are false and D is true.
 Question 23
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively. The automation which recognizes the language L(P) ∩ L(Q) is :
 A B C D
Theory-of-Computation       Finite-Automata       Gate 2007-IT
Question 23 Explanation:
String 'aa' is accepted by both FA, P and Q. And FA in option (A) also accepts string 'aa' and none of the other option FA accepts 'aa'. Hence option (A) is the answer.
 Question 24
Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this language is:
 A 3 B 5 C 8 D 9
Theory-of-Computation       Finite-Automata       Gate-2006
Question 24 Explanation:
L = (111 + 11111)* generates the strings {ϵ, 111, 11111, 111111, 11111111, …….}
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 25
In the automaton below, s is the start state and t is the only final state. Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true?
 A The automaton accepts u and v but not w B The automaton accepts each of u, v, and w C The automaton rejects each of u, v, and w D The automaton accepts u but rejects v and w
Theory-of-Computation       Finite-Automata       Gate 2006-IT
Question 25 Explanation:
(i) u = abbaba

where t is final state
(ii) v = bab

s is not final state
(iii) w = aabb

s is not final state
 Question 26
For a state machine with the following state diagram the expression for the next state S+ in terms of the current state S and the input variables x and y is
 A S+ = S’ . y’ + S . x B S+ =S. x . y’ + S’ . y . x’ C S+ =x . y’ D S+ =S’ . y + S . x’col
Theory-of-Computation       Finite-Automata       Gate 2006-IT
Question 26 Explanation:

From the table:
S' = S'y' + Sx
 Question 27
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?
 A It computes 1's complement of the input number B It computes 2's complement of the input number C It increments the input number D It decrements the input number
Theory-of-Computation       Finite-Automata       Gate-2005
Question 27 Explanation:
Let consider an example string:
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 28
Consider the machine M: The language recognized by M is :
 A {w ∈ {a, b}* | every a in w is followed by exactly two b's} B {w ∈ {a, b}*| every a in w is followed by at least two b’} C {w ∈ {a, b}*| w contains the substring 'abb'} D {w ∈ {a, b}*| w does not contain 'aa' as a substring}
Theory-of-Computation       Finite-Automata       Gate-2005
Question 28 Explanation:
Option A: It is false. The string with more than two b's also accepting the string.
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 29

 A divisible by 3 and 2 B odd and even C even and odd D divisible by 2 and 3
Theory-of-Computation       Finite-Automata       Gate-2004
Question 29 Explanation:
Option B:
For example 001 consists of even no. of zero's and odd no. of one's. It is not accepted by TM.
So, it is false.
Option C:
For example 110, contains even 1's and odd 0's but not accepted by TM.
So, it is false.
Option D:
For example 11000, where no. of 1's divisible by '2', and no. of zero's divisible by 3, but not accepted by TM.
So, it is false.
Option A:
It accepts all string where no. of 1's divisible by 3, and no. of zero's divisible by 2.
It is true.
 Question 30
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
 A 1 B 5 C 7 D 8
Theory-of-Computation       Finite-Automata       Gate-2003
Question 30 Explanation:

There are possible: 7 strings
 Question 31
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 ?
 A L1 = {0,1}* - L B L1 = {0,1}* C L1 ⊆ L D L1 = L
Theory-of-Computation       Finite-Automata       Gate-2003
Question 31 Explanation:
As in the question said,

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

 A Outputs the sum of the present and the previous bits of the input. B Outputs 01 whenever the input sequence contains 11 C Outputs 00 whenever the input sequence contains 10 D None of the above
Theory-of-Computation       Finite-Automata       Gate-2002
Question 32 Explanation:
Let us consider a string 100111
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10
 Question 33
The smallest finite automaton which accepts the language {x|length of x is divisible by 3} has
 A 2 states B 3 states C 4 states D 5 states
Theory-of-Computation       Finite-Automata       Gate-2002
Question 33 Explanation:
{x | length of x divisible by 3} for this constructing a finite Automata that implies

Minimum no. of states that we require is "3".
 Question 34
 A Theory Explanation is given below.
Theory-of-Computation       Finite-Automata       Gate-2002
 Question 35
What can be said about a regular language L over {a} whose minimal finite state automation has two states?
 A L must be {an |n is odd} B L must be {an |n is even} C L must be {an|≥0} D Either L must be {an |n is odd}, or L must be {an | n is even}
Theory-of-Computation       Finite-Automata       Gate-2000
Question 35 Explanation:
If first state is final, then it accepts even no. of a's. If second state is final then it accepts odd no. of a's.
 Question 36
Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite  automation  that  recognizes  the  language  represented  by  this  regular expression contains
 A n states B n + 1 states C n + 2 states D None of the above
Theory-of-Computation       Finite-Automata       Gate-1999
Question 36 Explanation:
Let's draw both NFA and DFA and see which one requires less no. of state.
DFA:

So, DFA requires (n+2) state.
NFA:

So, NFA requires (n+1) state.
min(n+1, n+2)
= n+1
 Question 37
Which of the following set can be recognized by a Deterministic Finite state Automaton?
 A The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary B The numbers 1, 2, 4, ………………., 2n, …………..written in unary C The set of binary string in which the number of zeros is the same as the number of ones D The set {1, 101, 11011, 1110111, ………..}
Theory-of-Computation       Finite-Automata       Gate-1998
Question 37 Explanation:
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is reguar and recognized by deterministic finite automata.
 Question 38

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite automaton accepting L is

 A 2 B 5 C 8 D 3
Theory-of-Computation       Finite-Automata       Gate-1998
Question 38 Explanation:
NFA:

Equivalent DFA:

Hence, 5 states.
 Question 39

 A 4 B 3 C 2 D 1
Theory-of-Computation       Finite-Automata       Gate-1996
Question 39 Explanation:
3 states are required in the minimized machine states B and C can be combined as follows:
 Question 40

 A L=0*1*
Theory-of-Computation       Finite-Automata       Gate-1994
Question 40 Explanation:
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
 Question 41

 A B C D E
Theory-of-Computation       Finite-Automata       Gate-1993
 Question 42
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
 A N2 B 2N C 2N D N!
Theory-of-Computation       Finite-Automata       Gate-2001
Question 42 Explanation:
If NFA contains N, then possible number of states in possible DFA is 2N.
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
 Question 43
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?
 A 8 B 14 C 15 D 48
Theory-of-Computation       Finite-Automata       Gate-2001
Question 43 Explanation:
A DFA which is no. of a's divisible by 6 consists of 6 states i.e., mod6 results 0,1,2,3,4,5.
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
 Question 44

 A Theory Explanation is given below.
Theory-of-Computation       Finite-Automata       Gate-2001
 Question 45
A minimal DFA that is equiavlent to an NDFA with n nodes has always 2n states.
 A True B False
Theory-of-Computation       Finite-Automata       GATE-1987
Question 45 Explanation:
A minimal DFA is equivalent to a NDFA with n nodes has atmost 2n states and does not have always 2n states.
There are 45 questions to complete.