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

This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Non-deterministic Finite Automata – 1”.

1. Which NDFA correctly represents the following RE?

` a(bab)*∪a(ba)* `

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

Explanation: We can verify that the string ababa is accepted by this NFA once we “guess” the state path q0, q2, q5, q2, q5, q2 ∈ F. Of course the only choice is the first one. If we made the wrong start q0, q1, q3, q4, q1 we reach a point where we have a remaining a to process with no place to go. This is a failure.

2. Which is the correct NDFA for the following mentioned expression?

`(ab)*∪(aba)*`

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

Explanation: A ε transition takes no input and represents a pure nondeterministic choice of being in the state or the target state without having done any processing.

3. NDFAs where introduced by ____________
a) Michael O Rabin & Dana Scott
b) Dan Brown
c) Sun micro system Labs
d) SAP Labs

Explanation: NFAs were introduced Dana Scott and Michael O. Rabin who also showed their equivalence to DFAs.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

4. The regular languages are not closed under ___________
a) Concatenation
b) Union
c) Kleene star
d) Complement

Explanation: RE are closed under

• Union (cf. picture)
• Intersection
• Concatenation
• Negation
• Kleene closure.
• 5. The Tuples for NDFA is ___________
a) ∑, Q, q0, F, δ
b) Q, q0, F, δ
c) Θ, Q, q0, F,δ
d) F, Q, Δ, q0, δ

Explanation: An NFA is represented formally by a 5-tuple, (Q, Σ, Δ, q0, F), of

• a set of states Q
• a set of input symbols Σ
• a transition function Δ : Q × Σ → P(Q).
• an initial state q0 ∈ Q
• a final state F ⊆ Q.

6. NFAs are ________ DFAs.
a) Larger than
b) More expressive than
c) Less expressive than
d) Equally expressive as

Explanation: Because there is more number of states for an NDFA than for a DFA for a given expression.

7. An NFA’s transition function returns ________
a) A Boolean value
b) A state
c) A set of states
d) An edge

Explanation: A transition function Δ: Q × Σ → P (Q).Where P (Q) denotes the power set of Q.

Sanfoundry Global Education & Learning Series – Compilers.

To practice all areas of Compilers, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]