This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Applications of DFA”.
1. Given Language: {x | it is divisible by 3}
The total number of final states to be assumed in order to pass the number constituting {0, 1} is
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The DFA for the given language can be constructed as follows:
2. A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011
View Answer
Explanation: If the string is divisible by four, it surely ends with the substring ‘100’ while a binary string divisible by 2 would surely end with the substring ‘10’.
3. Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.
a) 16
b) 11
c) 5
d) 6
View Answer
Explanation: If L leads to FA1, then for Lc, the FA can be obtained by exchanging the final and non-final states.
4. If L1 and L2 are regular languages, which among the following is an exception?
a) L1 U L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned
View Answer
Explanation: It the closure property of Regular language which lays down the following statement:
If L1, L2 are 2- regular languages, then L1 U L2, L1 ∩ L2, L1C, L1 – L2 are regular language.
5. Predict the analogous operation for the given language:
A: {[p, q] | p ϵ A1, q does not belong to A2}
a) A1-A2
b) A2-A1
c) A1.A2
d) A1+A2
View Answer
Explanation: When set operation ‘-‘ is performed between two sets, it points to those values of prior set which belongs to it but not to the latter set analogous to basic subtraction operation.
6. Which among the following NFA’s is correct corresponding to the given Language?
L= {xϵ {0, 1} | 3rd bit from right is 0}
a) 
b) 
c) 
d) None of the mentioned
View Answer
Explanation: The NFA accepts all binary strings such that the third bit from right end is 1 and if not, is send to Dumping state. Note: It is assumed that the input is given from the right end bit by bit.
7. Statement 1: NFA computes the string along parallel paths.
Statement 2: An input can be accepted at more than one place in an NFA.
Which among the following options are most appropriate?
a) Statement 1 is true while 2 is not
b) Statement 1 is false while is not
c) Statement 1 and 2, both are true
d) Statement 1 and 2, both are false
View Answer
Explanation: While the machine runs on some input string, if it has the choice to split, it goes in all possible way and each one is different copy of the machine. The machine takes subsequent choice to split further giving rise to more copies of the machine getting each copy run parallel. If any one copy of the machine accepts the strings, then NFA accepts, otherwise it rejects.
8. Which of the following options is correct for the given statement?
Statement: If K is the number of states in NFA, the DFA simulating the same language would have states less than 2k.
a) True
b) False
View Answer
Explanation: If K is the number of states in NFA, the DFA simulating the same language would have states equal to or less than 2k.
9. Let N (Q, ∑, δ, q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, ∑, δ’, q0’, A’), which among the following is true?
a) Q’ = P(Q)
b) Δ’ = δ’ (R, a) = {q ϵ Q | q ϵ δ (r, a), for some r ϵ R}
c) Q’ = {q0}
d) All of the mentioned
View Answer
Explanation: All the optioned mentioned are the instruction formats of how to convert a NFA to a DFA.
10. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?
a) 226
b) 224
c) 225
d) 223
View Answer
Explanation: The maximum number of states an equivalent DFA can comprise for its respective NFA with k states will be 2k.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice Computer Science MCQs
- Check Computer Science Books
- Apply for Computer Science Internship
- Check Automata Theory Books
