Compilers Interview Questions and Answers for freshers on “Non – Deterministic Finite Automata”.
1. Conversion of a DFA to an NFA __________
a) Is impossible
b) Requires the subset construction
c) Is Chancy
d) Is nondeterministic
Answer: b
Clarification: In order to convert NDFA to DFA we work with sets of state where each state in the DFA corresponds to a set of NFA states.
2. A regular language corresponds to __________
a) An alphabet
b) Set of strings over an alphabet
c) A DFA only
d) A DFA or an NFA
Answer: b
Clarification: A regular grammar takes in all strings over an alphabet.
3. An NFA may be converted to a DFA using __________
a) Induction
b) A construction
c) Contradiction
d) Compilation
Answer: b
Clarification: subset construction is used to convert a NFA into DFA.
4. The subset construction shows that every NFA accepts a __________
a) String
b) Function
c) Regular language
d) Context-free language
Answer: c
Clarification: Like DFAs, NFAs only recognize regular languages.
5. Which is the application of NFA?
a) A regular language is produced by union of two regular languages
b) The concatenation of two regular languages is regular
c) The Kleene closure of a regular language is regular
d) All of the mentioned
Answer: d
Clarification: As per its definition.
6. For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
a) True
b) False
Answer: a
Clarification: Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a simpler machine. Which is executed by using the powerset construction.
7. Like DFAs, NFAs only recognize regular languages.
a) True
b) False
Answer: a
Clarification: It is a known fact.