## Finite-Automata

 Question 1

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 1 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 2
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 2 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 3

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 3 Explanation:
The NFA for regular expression: (a+b)*b(a+b) After converting the NFA into DFA: After converting the NFA into DFA: Question 4

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 4 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 5
 A {q0,q1,q2 } B {q0,q1 } C {q0,q1,q2,q3 } D {q3 }
Theory-of-Computation       Finite-Automata       GATE 2014(Set-01)
Question 5 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 6
 A ∅ B {ε} C a* D {a ,ε}
Theory-of-Computation       Finite-Automata       Gate 2012
Question 6 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 7
 A B C D Theory-of-Computation       Finite-Automata       Gate 2012
Question 7 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 8
 A k+1 B n+1 C 2n+1 D 2k+1
Theory-of-Computation       Finite-Automata       Gate 2011
Question 8 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 9
 A B C D Theory of Computation        Finite-Automata       Gate 2011
Question 9 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 10
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 10 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 11
 A 3 B 4 C 5 D 6
Theory-of-Computation       Finite-Automata       2009
Question 11 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 12
 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 12 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 13
 A B C D Theory-of-Computation       Finite-Automata       Gate-2008
Question 13 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 14
 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 14 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 15
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 15 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 16
 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 16 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 17
 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 17 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 18
 A 15 states B 11 states C 10 states D 9 states
Theory-of-Computation       Finite-Automata       Gate-2007
Question 18 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 19
 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 19 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 20
 A 1 B 2 C 3 D 4
Theory-of-Computation       Finite-Automata       Gate-2007
Question 20 Explanation:
The minimum state automaton for problem 74 is: Question 21
 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 21 Explanation:
Just simulate the running of the DFA on all options - A, B and C are false and D is true.
 Question 22
 A B C D Theory-of-Computation       Finite-Automata       Gate 2007-IT
Question 22 Explanation:
String 'aca' 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 23
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 23 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 24
 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 24 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 25
 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 25 Explanation: From the table:
S' = S'y' + Sx
 Question 26
 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 26 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 27
 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 27 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 28
 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 28 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 29
 A {A→aB, A→bA, B→bA, B→aA, B→ε} B {A→aA, A→bB, B→bB, B→aA, B→ε} C {A→bB, A→aB, B→aA, B→bA, A→ε} D {A→aA, A→bA, B→bB, B→aA, A→ε}
Theory-of-Computation       Finite-Automata       Gate 2004-IT
 Question 30
 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
 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.
So, final answer will be,
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 0 state 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.