COMPUTER SCIENCE AND ENGINEERING
COMPILER DESIGN
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
A Boolean value
|
|
|
A state
|
|
|
A set of states
|
|
|
An edge
|
Detailed explanation-1: -1 Answer. To explain: A transition function : Q × → P (Q).
Detailed explanation-2: -In a DFA, the transition function always returns a single state; in an NFA, the transition function returns a set of states, which could be empty, or all of Q, or anything in between. ∗(r, x) if w = ax.
Detailed explanation-3: -For an arbitrary NFA with N states, the maximum number of states in an equivalent minimized DFA is 2N. Q. Consider the following deterministic finite automata (DFA).
Detailed explanation-4: -A transition on reading means that the NFA-makes the transition without reading any symbol in the input. Thus the tape head does not move when is read. Note that any NFA is also a NFA-.
Detailed explanation-5: -A two-state NFA with both states final where the minimal equivalent DFA has 4 states. Theorem 10.