This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Language of NFA”.
1. Subset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) ε-NFA to NFA
View Answer
Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.
2. Given Language:
Ln= {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}
How many state are required to execute L3 using NFA?
a) 16
b) 15
c) 8
d) 7
View Answer
Explanation: The finite automaton for the given language is made and thus, the answer can be obtained.
3. Which of the following does the given NFA represent?
a) {11, 101} * {01}
b) {110, 01} * {11}
c) {11, 110} * {0}
d) {00, 110} * {1}
View Answer
Explanation: The given diagram can be analysed and thus the option can be seeked.
4. The number of transitions required to convert the following into equivalents DFA:
a) 2
b) 3
c) 1
d) 0
View Answer
5. If L is a regular language, Lc and Lr both will be:
a) Accepted by NFA
b) Rejected by NFA
c) One of them will be accepted
d) Cannot be said
View Answer
Explanation: If L is a regular Language, Lc and Lr both are regular even.
6. In NFA, this very state is like dead-end non final state:
a) ACCEPT
b) REJECT
c) DISTINCT
d) START
View Answer
Explanation: REJECT state will be like a halting state which rejects a particular invalid input.
7. We can represent one language in more one FSMs, true or false?
a) TRUE
b) FALSE
c) May be true
d) Cannot be said
View Answer
Explanation: We can represent one language in more one FSMs, example for a same language we have a DFA and an equivalent NFA.
8. The production of form non-terminal -> ε is called:
a) Sigma Production
b) Null Production
c) Epsilon Production
d) All of the mentioned
View Answer
Explanation: The production of form non-terminal ->ε is call null production.
9. Which of the following is a regular language?
a) String whose length is a sequence of prime numbers
b) String with substring wwr in between
c) Palindrome string
d) String with even number of Zero’s
View Answer
Explanation: DFSM’s for the first three option is not possible; hence they aren’t regular.
10. Which of the following recognizes the same formal language as of DFA and NFA?
a) Power set Construction
b) Subset Construction
c) Robin-Scott Construction
d) All of the mentioned
View Answer
Explanation: All the three option refers to same technique if distinguishing similar constructions for different type of automata.
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.
- Apply for Automata Theory Internship
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Buy Computer Science Books
- Buy Automata Theory Books