This set of Compilers Interview Questions and Answers for freshers focuses on “Non – Deterministic Finite Automata – 2”.
1. Conversion of a DFA to an NFA __________
a) Is impossible
b) Requires the subset construction
c) Is Chancy
d) Is nondeterministic
Explanation: 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
Explanation: A regular grammar takes in all strings over an alphabet.
3. An NFA may be converted to a DFA using __________
b) A construction
Explanation: subset construction is used to convert a NFA into DFA.
4. The subset construction shows that every NFA accepts a __________
c) Regular language
d) Context-free language
Explanation: Like DFAs, NFAs only recognize regular languages.
5. Construct a NDFA for the following regular expression.
Explanation: The NDFA initially takes either a or b followed by a then b then reaches the final state or takes iterations of a or b to reach the final state.
6. 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
Explanation: As per its definition.
7. For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
Explanation: 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.
8. Like DFAs, NFAs only recognize regular languages.
Explanation: It is a known fact.
Sanfoundry Global Education & Learning Series – Compilers.
To practice all areas of Compilers for Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers.