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.
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.
8.
Which NDFA correctly represents the following RE?
a(bab)*∪a(ba)*
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.
9.
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.
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.
10.
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.
