Automata Theory Questions and Answers – The Language of NFA

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

Answer: a
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

Answer: b
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?
The given diagram represents {11, 110} * {0} the given NFA
a) {11, 101} * {01}
b) {110, 01} * {11}
c) {11, 110} * {0}
d) {00, 110} * {1}
View Answer

Answer: c
Explanation: The given diagram can be analysed and thus the option can be seeked.
advertisement
advertisement

4. The number of transitions required to convert the following into equivalents DFA:
The number of transitions required to convert is 2
a) 2
b) 3
c) 1
d) 0
View Answer

Answer: a
Explanation:
Transitions required to convert the following into equivalents DFA

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

Answer: a
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

Answer: b
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

Answer: a
Explanation: We can represent one language in more one FSMs, example for a same language we have a DFA and an equivalent NFA.
advertisement

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

Answer: b
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

Answer: d
Explanation: DFSM’s for the first three option is not possible; hence they aren’t regular.
advertisement

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

Answer: d
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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.