FiniteAutomata
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 = x_{1} x_{2} ... x_{n} ∈ Σ^{n}, n ≥ 0. Let π(x) = x_{1} º x_{2} º ... º x_{n}.
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 ≥ 2^{n}  
k ≥ n  
k ≤ n^{2}  
k ≤ 2^{n}

In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2^{n} states.
Hence k ≤ 2^{n} is necessarily true.
Question 3 
L^{0} = {ε}
L^{i} = L^{i1}∙L for all i>0
The order of a language L is defined as the smallest k such that L^{k} = L^{k+1}.
Consider the language L_{1} (over alphabet 0) accepted by the following automaton.
The order of L_{1} is ______.
2  
3  
4  
5 
Now L_{1}^{0} = ϵ and L_{1}^{1} = ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L_{1}
Now L_{1}^{2} = L_{1}^{1} .
L_{1} = L_{1} .
L_{1} = (ϵ + 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 L_{1}^{3} = L_{1}^{2} .
L_{1} = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L_{1}^{2} = L_{1}^{3}
Or L_{1}^{2} = L_{1}^{2+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 finitestate 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 → aXa Y → aYbϵ
{a^{m} b^{n} │ m ≥ n, n > 0}  
{a^{m} b^{n} │ m ≥ n, n ≥ 0}  
{a^{m} b^{n} │ m > n, n ≥ 0}  
{a^{m} b^{n} │ 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 {a^{m} b^{n}│m>n,n≥0}.
Question 6 
Consider the finite automaton in the following figure.
What is the set of reachable states for the input string 0011?
{q_{0}, q_{1}, q_{2}}  
{q_{0}, q_{1}}  
{q_{0}, q_{1}, q_{2}, q_{3}}  
{q_{3}} 
{q_{0} , 0 → q_{0}} , { q_{0} , 0 → q_{0} }, {q_{0} , 1 → q_{0}}, {q_{0} , 1 → q_{1}} . Hence δ (q_{0}, 0011) = q_{1}
{q_{0} , 0 → q_{0}} , { q_{0} , 0 → q_{0} }, {q_{0} , 1 → q_{1}}, {q_{1} , 1 → q_{2}} . Hence δ (q_{0}, 0011) = q_{2}
Hence δ (q_{0}, 0011) = {q_{0}, q_{1}, q_{2}}
Question 7 
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 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
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 following.
L = {a^{nk} 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  
2^{n+1}  
2^{k+1} 
So lets check of n = 2,
L = a_{2k}, 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 a^{nk}, (n+1) states will be required.
Question 10 
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 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 nondeterministic finite automaton that accepts L?
n1  
n  
n+1  
2^{n1} 
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 
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 15 
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 *
P2, Q1, R3, S4
 
P1, Q3, R2, S4  
P1, Q2, R3, S4  
P3, Q2, R1, S4 
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 
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 17 
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 18 
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 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 
The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.
divisible by 3 and 2  
odd and even  
even and odd  
divisible by 2 and 3 
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 23 
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 24 
Consider the NFA M shown below.
Let the language accepted by M be L. Let L_{1} be the language accepted by the NFA M_{1}, obtained by changing the accepting state of M to a nonaccepting state and by changing the nonaccepting state of M to accepting states. Which of the following statements is true?
L_{1} = {0,1}*  L  
L_{1} = {0,1}*  
L_{1} ⊆ L  
L_{1} = L 
As in above NFA language,
L_{1} is {0,1}*.
Question 25 
The Finite state machine described by the following state diagram with A as starting state, where an arc label is x/y and x stands for 1bit input and y stands for 2 bit output
Outputs the sum of the present and the previous bits of the input.  
Outputs 01 whenever the input sequence contains 11  
Outputs 00 whenever the input sequence contains 10  
None of the above 
(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 26 
The smallest finite automaton which accepts the language {xlength of x is divisible by 3} has
2 states  
3 states  
4 states  
5 states 
Minimum no. of states that we require is "3".
Question 27 
We require a four state automaton to recognize the regular expression (ab)*abb.
 (a) Give an NFA for this purpose.
(b) Give a DFA for this purpose.
Theory Explanation is given below. 
Question 28 
Given an arbitrary nondeterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
N^{2}  
2^{N}  
2N  
N! 
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 2^{2} = 2^{N}
Question 29 
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?
8  
14  
15  
48 
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
Question 30 
Construct DFA’s for the following languages:
(a) L = {ww ∈ {a,b}*, w has baab as a subsring } (b) L = {ww ∈ {a,b}*, w has an odd number of a's and an odd number of b's}
Theory Explanation is given below. 
Question 31 
What can be said about a regular language L over {a} whose minimal finite state automation has two states?
L must be {a^{n} n is odd}  
L must be {a^{n} n is even}  
L must be {a^{n}≥0}  
Either L must be {a^{n} n is odd}, or L must be {a^{n}  n is even} 
Question 32 
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
n states  
n + 1 states  
n + 2 states  
None of the above 
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 33 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
The numbers 1, 2, 4, 8, ……………., 2^{n}, ………… written in binary  
The numbers 1, 2, 4, ………………., 2^{n}, …………..written in unary  
The set of binary string in which the number of zeros is the same as the number of ones  
The set {1, 101, 11011, 1110111, ………..} 
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 34 
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
2  
5  
8  
3 
Equivalent DFA:
Hence, 5 states.
Question 35 
Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be
4  
3  
2  
1 
Question 36 
The regular expression for the language recognized by the finite state automaton of figure is __________
L = 0*1* 
L contains all binary strings where a 1 is not followed by a 0.
Question 37 
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 ______.
6 
DFA 1: No. of a’s not divisible by 3
Using product automata:
Question 38 
If the state machine described in figure, should have a stable state, the restriction on the inputs is given by
Question 39 
Which of the following three statements are true? Prove your answer.
 (i) The union of two recursive languages is recursive.
(ii) The language {O"n is a prime} is not regular.
(iii) Regular languages are closed under infinite union.
Theory Explanation. 
Question 40 
A minimal DFA that is equivalent to an NDFA with n nodes has always 2^{n} states.
True  
False 
Question 41 
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?
m ≤ 2^{n}  
n ≤ m  
M has one accept state  
m = 2^{n} 
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2^{n}
→ m ≤ 2^{n}
Question 42 
If the final states and nonfinal 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?
Set of all strings that do not end with ab  
Set of all strings that begin with either an a or a b  
Set of all strings that do not contain the substring ab  
The set described by the regular expression b*aa*(ba)*b* 
Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepted by RE and it belongs to b*aa*(ba)*b*.
Question 43 
Consider the following two finite automata. M_{1} accepts L_{1} and M_{2} accepts L_{2}.
Which one of the following is TRUE?L_{1} = L_{2}  
L_{1} ⊂ L_{2}  
L_{1} ∩ L_{2}‘ = ∅  
L_{1} ∪ L_{2} ≠ L_{1}  
A and C 
L_{2} = (0=1)* 11(0+1)*
Both L_{1} and L_{2} are equal.
Option A is correct.
→ L_{1} ∩ L_{2}‘ = L_{1} ∩ L_{1}‘ = ∅ (option C also correct)
Question 44 
Consider the following DFA in which s_{0} is the start state and s_{1}, s_{3} are the final states.
What language does this DFA recognize ?
All strings of x and y  
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  
All strings of x and y which have equal number of x and y  
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 
Question 45 
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:
Question 46 
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?
The automaton accepts u and v but not w  
The automaton accepts each of u, v, and w  
The automaton rejects each of u, v, and w  
The automaton accepts u but rejects v and w 
where t is final state
(ii) v = bab
s is not final state
(iii) w = aabb
s is not final state
Question 47 
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
S^{+} = S’ . y’ + S . x  
S^{+} = S. x . y’ + S’ . y . x’  
S^{+} = x . y’  
S^{+} = S’ . y + S . x’col 
From the table:
S' = S'y' + Sx
Question 48 
Let M = {K,Σ,δ,s,F} be a finite state automaton, where
K = {A,B}, Σ = {a,b}, s = A, F = {B}, δ(A,a) = A, δ(A,b) = B, δ(B,a) = B and δ(B,a) = A
A grammar to generate the language accepts by M can be specified as G = (V,Σ,R,S), where V = K∪Σ, and S = A.
Which one of the following set to rules will make L(G) = L(M)?
{A→aB, A→bA, B→bA, B→aA, B→ε}  
{A→aA, A→bB, B→bB, B→aA, B→ε}  
{A→bB, A→aB, B→aA, B→bA, A→ε}  
{A→aA, A→bA, B→bB, B→aA, A→ε} 
Question 49 
Complements a given bit pattern  
Finds 2’s complement of a given bit pattern  
Increments a given bit pattern by 1  
Changes the sign bit 
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 50 
without rewinding capability and unidirectional tape movement  
rewinding capability and unidirectional tape movement  
without rewinding capability and bidirectional tape movement  
rewinding capability and bidirectional tape movement 
→ The finite state machine has less computational power than some other models of computation such as the Turing machine.
→ The computational power distinction means there are computational tasks that a Turing machine can do but a FSM cannot. This is because a FSM's memory is limited by the number of states it has.
→ A finite state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. That is, each formal language accepted by a finite state machine is accepted by such a kind of restricted Turing machine, and vice versa.
Question 51 
m x 2^{n}  
2^{m+n}  
2^{mn}  
m+n 
Generally FSM consists of 2^{x} states for a given input x.
But in the question, the input is specified number of words and length of each word.
For a given, ‘m’ words, each of length ‘n’ bits, so total number of bits are m*n
So, total number of states required by a Finite State Machine are 2^{mn}.
Question 52 
7  
9  
10  
11 
String which consists of 0’s and 1’s
Language is number of 0’s is divisible by 2 and number of 1’s is divisible by 5
Machine is minimum state deterministic finite automaton
The set of strings generated by {0,1} are ={ε,0,1,00,11,01,10,000,011,010 .. and so on}
The strings which are generated by language which is specified in the questions are
{ ε , 00, 11111, 0011111, 0011111 , 1111100, 1010111 , 000011111,….and so on }
So, strings accepted by the automaton have to be of length 0, 2, 4, 5, 6, 7, 8, 9, 10, 11, 14, 12….and so on, i.e. equation for length will be 2x + 5y (where x,y>=0 )
Number of 0’s divisible by 2 means , the possible remainders are 0 and 1 i.e; 2
Number of 1’s divisible by 5 means , the possible remainders are 4,3,2,1,0 i.e; 5
Total number of states are 2*5 =10
Question 53 
{1, 0}* {01}  
{1, 0}* {1}  
{1}{1, 0}* {1}  
1*0* {0, 1} 
Question 54 
Let denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in that are accepted by M is
0  
1  
2  
3 
01110110
01110111
Above two strings are are having constraint that 2nd, 3rd, 6th and 7th bits are 1. So, it satisfied above condition.
Question 55 
Consider the following two languages:
 L_{1} = {x  for some y with y=2^{x}, xy ∈ L and L is regular language}
L_{2} = { x  for some y such that x = y, xy∈L and L is regular language}
Which one of the following is correct?
Both L_{1} and L_{2} are regular languages
 
Both L_{1} and L_{2} are not regular languages
 
Only L_{1} is regular language  
Only L_{2} is regular language

Consider a language L= {a^{3n}  n ≥ 0} , the strings in L are {ϵ, aaa, aaaaaa, …….}
then L_{1} = {a^{n}  n ≥ 0} as every string in L can be broken into three equal parts.
DFA for L:
DFA for L_{1}:
By same logic L_{2} is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L_{1}, since we can break only even length string into two equal parts such that x = y if “xy ∈ L”.
Question 56 
have same number of states  
have same number of edges  
have same number of states and edges  
recognized same set of tokens 
Question 57 
1.∅
2.{∈}
3.a*
4.{a, ∈}
1  
2  
3  
4 
Hence the complement of language is: {a* − a+} = {ϵ}
Question 58 
regular language  
context free language  
context sensitive language  
recursive enumeration language 
Question 59 
FSA cannot remember arbitrarily large amount of information  
FSA cannot deterministically fix the midpoint  
Even if the midPoint is known an FSA cannot find whether the second half of the matches the first half  
All of the above 
Question 60 
A DFA can be expressed as a 5 tuple(Q, Σ, δ, q_{0}, F), where δ is the transition function defined as ___?
δ: Σ → Q
 
δ: Q x Q → Σ  
δ: Q → Q
 
δ: Q x Σ → Q

DFA consists of 5 tuples {Q, ∑, q, F, δ}.
Q : set of all states.
∑ : set of input symbols. (Symbols which machine takes as input)
q : Initial state. (Starting state of a machine)
F : set of final state.
δ : Transition Function, defined as δ: QX∑ → Q.
Question 61 
Power of deterministic automata is equivalent to power of nondeterministic automata.  
Power of deterministic pushdown automata is equivalent to power of nondeterministic pushdown automata.  
Power of deterministic turing machine is equivalent to power of nondeterministic turing machine.  
All the above 
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
Question 62 
(i) Whether a finite automaton halts on all inputs?
(ii) Whether a given Context Free Language is Regular?
(iii) Whether a Turing Machine computes the product of two numbers?
Which one of the following is correct?
Only (ii) and (iii) are undecidable problems  
(i), (ii) and (iii) are undecidable problems  
Only (i) and (ii) are undecidable problems  
Only (i) and (iii) are undecidable problems 
● Regular languages are useful for many practical applications due to the fact that “all natural” questions concerning regular languages are decidable
Question 63 
L = { 2 _{nk}  k > 0 , and n is non − n egative integer number }
The minimum number of states of finite automaton which accept the language L is
n  
n+1  
2 ^{n}  
n (n + 1 )/2 
assume n= 2 (for instance)
then we have : L= a ^{2k}  k>0
so k's value will be {1,2,3,4,........} and accordingly in L we have strings {a ^{2} ,a^{ 4} ,a^{ 6} , a^{ 8} .......}
→ It is clearly even number of a's (except zero a's) and for this we have 3 state DFA,
→ If n=3 then we will have a ^{3} , a^{ 6} , a^{ 9} ..........
→ So, we require 4 state DFA
hence answer will be "n+1" states are required.
Question 64 
Have the same number of edges  
Have the same number of states  
Recognize the same set of tokens  
Have the same number of states and edges 
Question 65 
any string of odd number of a’s  
any string of odd number of b’s  
any string of even number of a’s and odd number of b’s  
any string of odd number of a’s and odd number of b’s 
L = {ab,ba,ababab, bababa,..........}
Here L is the language containing odd number of a’s and odd number of b’s.
Question 66 
Q  
2Q  
2Q – 1  
2Q 
Question 67 
The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
5  
4  
3  
2 
Now minimize the above DFA ( state q and s are equivalent and hence can be merged)
The min DFA will have 4 states.
Question 68 
of finite tape length, rewinding capability and unidirectional tape movement.  
of finite tape length, without rewinding capability and unidirectional tape movement.  
of finite tape length, without rewinding capability and bidirectional tape movement.  
of finite tape length, rewinding capability and bidirectional tape movement. 
Question 69 
Descriptive Explanation 
(i) For a binary string x, x ∈ L n iff val (x) mod n = 0.
(ii) if val (x) = i mod n for a binary string x, then val (xb) ≡ (2i + b) mod n, for b = 0, 1.
So to construct a DFA for L_{ n} , it suffices to take n states q _{0} , . . . , q_{ n−1} , with q i recording the fact that the value of the string read so far is i mod n. Under this interpretation, q_{ 0} will be the initial and (only) final state, and the automaton will transition from state q _{i} to q_{ j} on reading letter b ∈ {0, 1}, where j = (2i + b) mod n.
The reader can construct the automaton for L_{ 4} in a similar manner. Or one could observe that L _{4} = {0, 1} ∗ {00} and construct a simpler automaton.
Finally, the language in question is L _{4} ∪ L_{ 5} , for which one can appeal to the closure of regular languages under union (and provide the appropriate NFA).
Question 70 
Descriptive Explanation 
Question 71 
Descriptive Explanation 
For each pair of states (r, s) ∈ R × S, A _{r,s} is obtained from A by keeping the set of states and set of transitions unchanged, but making r the unique intial state and s the unique final state.
If u ∈ L(A _{r,s} ), then there must be a word xuy ∈ L(A), where x labels the path from the initial state to r (r ∈ R is reachable from the initial state), u labels the path from r to s, and y labels the path from s to some final state of A (s ∈ S, so such a path must exist.)
Hence, output “Yes” if u ∈ L(A _{r,s} ) for some (r, s) ∈ R × S, and “No” otherwise.
Question 72 
Set of all strings containing ‘ab’  
Set of all strings containing ‘aab’  
Set of all strings ending in ‘abab’  
None of the above 
Question 73 
Only context free grammar  
Only context sensitive grammar  
Only regular grammar  
any unambiguous grammar 
Question 74 
2  
4  
5  
6 
Question 75 
64  
56  
1024  
5832 
Question 76 
1 final state among 5 states  
4 final states among 5 states  
1 final state among 6 states  
5 final states among 6 states 
Question 77 
q _{0} and q_{ 0} respectively  
q _{0} and q_{ 1} respectively  
q _{0} and q_{ 2} respectively  
q _{0} and q_{ 3} respectively 
Question 78 
3  
4  
5  
6 
Question 79 
Consider the FA shown in fig below which language is accepted by the FA:
(a+b)*a  
b+(a+b)*b  
b+a*b*  
b+a*b

Option C  ‘b’ is generated which is not accepted by the given FA.
Option D ‘b’ is generated which is not accepted by the given FA.
Option A All the strings generated by regular expression are accepted by the given FA.
Moreover we can clearly see that given automata accepts all the strings which ends with ‘a’. And regular expression in option A generates all such strings.
Question 80 
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 state automaton accepting languages is ____
2  
5  
8  
3 
So the minimum state deterministic finite state automaton accepting language is 5.
Question 81 
Number of states in DFA accepting the following languages is:
L = {a^{n} b^{2m}  n, m>=1}
m  
n  
5  
2 
∴ No. of states in DFA for the language L = {a^{n}b^{2m}  n,m ≥ 1} is 5.
Question 82 
The language accepted by finite automata is the languages denoted by regular expressions.
 
For every DFA there is a regular expression denoting its language
 
For a regular expression r, there does not exist any NFA with transit that accepts L(r)  
None of these 
Question 83 
No  
Yes
 
Sometimes  
Depends of NFA

Question 84 
Have same number of states  
Have same number of edges
 
Have same number of states and edges  
Recognize same set of tokens 
Question 85 
States  
Edges  
States and Edges
 
None of the above 
Question 86 
2^{n}  
n  
n^{2}  
2^{n+1} 
Question 87 
CFG  
GNF  
RE  
CNF 
Question 88 
What is the language of the Nondeterministic Finite Automaton(NFA) on Σ={a,b} given below?
a* b*  
a· b'
 
a + b'
 
(ab)'  
None of the above 
A) The given expression generates ε , which is not generated by given automata.
B) The given automata can generate only b , which is not generated by the given regular expression.
C) The given automata can generate string ab which is not generated by given regular expression.
D) The given automata generates abab which cannot be generated by given automata.
Question 89 
Answer Questions 21  22 using the following Finite Automaton (FA) where the start S is state and T is the ending state:
The language accepted by the FA is:
(a + b)*(a + b)  
(a + b)*b  
(a + b)*a  
a*b 
Question 90 
Answer Questions 21  22 using the following Finite Automaton (FA) where the start S is state and T is the ending state:
In order to make the automaton shown above accept the string of length zero, the language of all words not ending with letter b (and also the null string), the following minor changes will suffice:
Make righthand state the start state and lefthand static the final state  
Make righthand state both the start and final state  
Make lefthand state both the start and final state  
Delete the lefthand state's selfloop labelled with b 
And we can clearly see that above automata accepts all the string not ending with ‘b’ and also accepts the empty string.
Question 91 
Let L be a language recognizable by a finite automaton. Determine the type of language realized by REVERSE(L)? Please justify your answer.
REVERSE (L)  {W such that W is the reverse of V where V Ɛ L}
Descriptive Solution 
Question 92 
P ::= QR
Q ::= c
Q ::= RcR
R ::= ddQ
Which of the following is False:
The length of every string produced by the grammar is even  
No string produced by the grammar has an odd number of consecutive d’s  
No string produced by the grammar has four consecutive d’s  
No string produced by the grammar has three consecutive c’s  
Every string produced by the grammar has at least has many d’s as c’s 