This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Non-deterministic Finite Automata – 1”.
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 startq0,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.
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.
4. The regular languages are not closed under
c) Kleene star
Explanation: RE are closed under
• Union (cf. picture)
• Kleene closure.
5. The Tuples for NDFA
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 a 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.