# 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

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

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}

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

Explanation:

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

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

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

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

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

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

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]