Automata Theory Multiple Choice Questions 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
Answer: a
Clarification: 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
Answer: b
Clarification: The finite automaton for the given language is made and thus, the answer can be obtained.
3. 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
Answer: d
Clarification: DFSM’s for the first three option is not possible; hence they aren’t regular.
4. 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
Answer: d
Clarification: All the three option refers to same technique if distinguishing similar constructions for different type of automata.
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
Answer: a
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: The production of form non-terminal ->ε is call null production.