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 ______.
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 |
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?
k ≥ 2n
| |
k ≥ n
| |
k ≤ n2 | |
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.
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 ______.
2 | |
3 | |
4 | |
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.
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 _________.
4 | |
5 | |
6 | |
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:
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|ϵ
{am bn │ m ≥ n, n > 0} | |
{am bn │ m ≥ n, n ≥ 0} | |
{am bn │ m > n, n ≥ 0} | |
{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}.
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?
What is the set of reachable states fot the input string 0011?{q0,q1,q2 } | |
{q0,q1 } | |
{q0,q1,q2,q3 } | |
{q3 } |
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}
{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* | |
{a ,ε} |
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+} = {ϵ}
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
The missing arcs in the DFA are
 | |
 | |
 | |
 |
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.
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?
What is the minimum number of states needed in a DFA to recognize L?k+1 | |
n+1 | |
2n+1 | |
2k+1 |
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.
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?
Which of the following finite state machines is a valid minimal DFA which accepts the same language as D? | |
 | |
 | |
 |
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.
(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?
n-1 | |
n | |
n+1 | |
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:
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?
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 |
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.
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 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?
Which of the following represents the product automaton Z×Y?
 | |
 | |
 | |
 |
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.
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 *
- e+ 0 (10 * 1 + 00) * 0
- e+ 0 (10 * 1 + 10) * 1
- e+ 0 (10 * 1 + 10) * 10 *
P-2, Q-1, R-3, S-4
| |
P-1, Q-3, R-2, S-4
| |
P-1, Q-2, R-3, S-4 | |
P-3, Q-2, R-1, S-4 |
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.
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?
m ≤ 2n | |
n ≤ m | |
M has one accept state | |
m = 2n |
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
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?
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* |
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?
Which one of the following is TRUE?L1 = L2 | |
L1 ⊂ L2 | |
L1 ∩ L2‘ = ∅ | |
L1 ∪ L2 ≠ L1 | |
A and C |
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)
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
15 states | |
11 states | |
10 states | |
9 states
|
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 |
b*ab*ab*ab* | |
(a+b)*
| |
b*a(a+b)* | |
b*ab*ab* |
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)* ”.
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
The language accepted by this automaton is given by the regular expression
1 | |
2 | |
3 | |
4 |
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 ?
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 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 :
The automation which recognizes the language L(P) ∩ L(Q) is :
 | |
 | |
 | |
 |
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:
3 | |
5 | |
8 | |
9 |
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.
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?
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 |
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
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
S+ = S’ . y’ + S . x | |
S+ =S. x . y’ + S’ . y . x’ | |
S+ =x . y’ | |
S+ =S’ . y + S . x’col |
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?
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
|
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.
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 :
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} |
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.
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 |
divisible by 3 and 2
| |
odd and even
| |
even and odd
| |
divisible by 2 and 3
|
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.
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
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 |
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 ?
L1 = {0,1}* - L
| |
L1 = {0,1}*
| |
L1 ⊆ L | |
L1 = L
|
Question 31 Explanation:
As in the question said,
As in above NFA language,
L1 is {0,1}*.
As in above NFA language,
L1 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 |
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
(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
2 states | |
3 states | |
4 states | |
5 states |
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".
Minimum no. of states that we require is "3".
Question 35 |
What can be said about a regular language L over {a} whose minimal finite state automation has two states?
L must be {an |n is odd} | |
L must be {an |n is even} | |
L must be {an|≥0} | |
Either L must be {an |n is odd}, or L must be {an | n is even} |
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
n states | |
n + 1 states | |
n + 2 states | |
None of the above |
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
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?
The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary | |
The numbers 1, 2, 4, ………………., 2n, …………..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, ………..} |
Question 37 Explanation:
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is reguar and recognized by deterministic finite automata.
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
2 | |
5 | |
8 | |
3 |
Question 38 Explanation:
NFA:
Equivalent DFA:
Hence, 5 states.
Equivalent DFA:
Hence, 5 states.
Question 39 |
4 | |
3 | |
2 | |
1 |
Question 39 Explanation:
3 states are required in the minimized machine states B and C can be combined as follows:
Question 40 |
L=0*1* |
Question 40 Explanation:
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
L contains all binary strings where a 1 is not followed by a 0.
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
N2 | |
2N | |
2N | |
N! |
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
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?
8 | |
14 | |
15 | |
48 |
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
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
Question 45 |
A minimal DFA that is equiavlent to an NDFA with n nodes has always 2n states.
True | |
False |
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.