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
View Answer

Answer: b
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
View Answer

Answer: b
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
c) Contradiction
d) Compilation
View Answer

Answer: b
Explanation: subset construction is used to convert a NFA into DFA.
advertisement
advertisement

4. The subset construction shows that every NFA accepts a __________
a) String
b) Function
c) Regular language
d) Context-free language
View Answer

Answer: c
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) Find the iterations from the given diagram
b) Find the either a or b from the given diagram
c) Find the final state from the given diagram
d) None of the mentioned
View Answer

Answer: a
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
View Answer

Answer: d
Explanation: As per its definition.
advertisement

7. For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
a) True
b) False
View Answer

Answer: a
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
View Answer

Answer: a
Explanation: It is a known fact.
advertisement

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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.