Compilers Multiple Choice Questions on “Non-deterministic Finite Automata”.
1. NFAs are ________ DFAs.
a) Larger than
b) More expressive than
c) Less expressive than
d) Equally expressive as
Answer: a
Clarification: Because there is more number of states for an NDFA than for a DFA for a given expression.
2. An NFA’s transition function returns ________
a) A Boolean value
b) A state
c) A set of states
d) An edge
Answer: c
Clarification: A transition function Δ: Q × Σ → P (Q).Where P (Q) denotes the power set of Q.
3. NDFAs where introduced by ____________
a) Michael O Rabin & Dana Scott
b) Dan Brown
c) Sun micro system Labs
d) SAP Labs
Answer: a
Clarification: NFAs were introduced Dana Scott and Michael O. Rabin who also showed their equivalence to DFAs.
4. The regular languages are not closed under ___________
a) Concatenation
b) Union
c) Kleene star
d) Complement
Answer: d
Clarification: 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, δ
Answer: a
Clarification: 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.