# Compilers Questions and Answers – Non-Deterministic Finite Automata – 2

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 __________
a) Induction
b) A construction
d) Compilation

Explanation: 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

Explanation: Like DFAs, NFAs only recognize regular languages.

5. Construct a NDFA for the following regular expression.

`(a∪b)*aba(a∪b)*`
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

a)
b)
c)
d) None of the mentioned

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.
a) True
b) False

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.
a) True
b) False

Explanation: It is a known fact.