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 ______.

A
120
B
136
C
125
D
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?

A
k ≥ 2n
B
k ≥ n
C
k ≤ n2
D
k ≤ 2n
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
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
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}
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

What is the complement of the language accepted by the NFA shown below?

Assume Σ={a} and ε is the empty string.

A
∅
B
{ε}
C
a*
D
{a ,ε}
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

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?

A
k+1
B
n+1
C
2n+1
D
2k+1
Question 7 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 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?

A
B
C
D
Question 8 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 9

Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?

A
{q0, q1, q2}
B
{q0, q1}
C
{q0, q1, q2, q3}
D
{q3}
Question 9 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 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

A
B
C
D
Question 10 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 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
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
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
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

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
Question 14 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 15

Consider the following Finite State Automaton.

The language accepted by this automaton is given by the regular expression

A
b*ab*ab*ab*
B
(a+b)*
C
b*a(a+b)*
D
b*ab*ab*
Question 15 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 16

Consider the following Finite State Automaton.

The minimum state automaton equivalent to the above FSA has the following number of states

A
1
B
2
C
3
D
4
Question 16 Explanation: 
The minimum state automaton for problem 74 is:
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?

A
B
C
D
Question 17 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}, where P 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 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 *
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
Question 18 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 19

Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

A
3
B
5
C
8
D
9
Question 19 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 20

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}
Question 20 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 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?

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
Question 21 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 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

A
1
B
5
C
7
D
8
Question 22 Explanation: 

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?

A
L1 = {0,1}* - L
B
L1 = {0,1}*
C
L1 ⊆ L
D
L1 = L
Question 23 Explanation: 
As in the question said,

As in above NFA language,
L1 is {0,1}*.
There are 23 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access