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) Find the NDFA from the given diagram
b) Find the string ababa from the given diagram
c) Find the tate path q0, q2 from the given diagram
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)*
advertisement
advertisement

a) Find the transition from the given diagram
b) Find the pure nondeterministic from the given diagram
c) Find the target state from the given diagram
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.
  • advertisement

    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.
    advertisement

    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]

    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.