FiniteAutomata
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?
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 2 
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 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 finitestate automation (DFA) accepting L is _________.
4  
5  
6  
7 
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 → 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 5 
{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 6 
∅  
{ε}  
a*  
{a ,ε} 
Hence the complement of language is: {a* − a^{+}} = {ϵ}
Question 7 
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 
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 9 
(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 
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 11 
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 12 
begin either with 0 or 1
 
end with 0
 
end with 00  
contain the substring 00 
Question 13 
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 
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 15 
m ≤ 2^{n}  
n ≤ m  
M has one accept state  
m = 2^{n} 
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2^{n}
→ m ≤ 2^{n}
Question 16 
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 accepetd by RE and it belongs to b*aa*(ba)*b*.
Question 17 
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 18 
15 states  
11 states  
10 states  
9 states

Question 19 
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 20 
1  
2  
3  
4 
Question 21 
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 22 
Question 23 
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 24 
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 25 
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 26 
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 27 
{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 28 
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 29 
{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 30 
1  
5  
7  
8 
There are possible: 7 strings
Question 31 
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 32 
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 33 
2 states  
3 states  
4 states  
5 states 
Minimum no. of states that we require is "3".
Question 35 
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 36 
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 37 
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 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
2  
5  
8  
3 
Equivalent DFA:
Hence, 5 states.
Question 39 
4  
3  
2  
1 
Question 40 
L=0*1* 
L contains all binary strings where a 1 is not followed by a 0.
Question 42 
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 43 
8  
14  
15  
48 
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
Question 45 
True  
False 