Non - Deterministic Finite Automata - Compilers Questions and Answers

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

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

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

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

Answer: d
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, δ
View Answer

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

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

Answer: c
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.

« Prev - Compilers Questions and Answers – Finite Automata – 2

» Next - Compilers Questions and Answers – Non-Deterministic Finite Automata – 2

Related Posts:

Recommended Articles: