Which of the following statements regarding NFA and DFA are TRUE?
$\Gamma, a stack alphabet$, is part of a PDA. A standard finite automaton uses Q, $\Sigma, \delta, q0$, and F.
How many states are in the minimal DFA accepting the language $L = { w$ in {a, b}* | w contains an even number of a's and an odd number of b's }?
The state space is {even_a, odd_a} x {even_b, odd_b}, giving 2 x 2 = 4 states.
In an NFA with $\epsilon-transitions (\epsilon-NFA) having 4 states {q0, q1, q2, q3}$, if $\epsilon-closure(q0) = {q0, q1, q2}, \delta(q1, 'a') = {q3}$, and $\delta(q2, 'a') = {q0}, how many states$ are in the $\epsilon-closure of delta_hat(q0, 'a')$?
The 'a' move from the $\epsilon-closure of q0 reaches {q0, q3}$. Its $\epsilon-closure$ is {q0,q1,q2,q3}, so 4 states are present.
The language $L = { w$ in {0, 1}* | the 3rd symbol from the right end is '1' } can be recognized by an NFA with how many states?
NFA states: start q0 (loops on 0,1), on '1' goes to q1, q1 on 0,1 to q2, q2 on 0,1 to q3 (accepting). Total 4 states. (An equivalent minimal DFA requires $2^3$ = 8 states).
How many states are in the minimal DFA accepting $L = { w$ in {0, 1}* | the 3rd symbol from the right end is '1' }?
A DFA must remember the last three bits, giving $2^3$ = 8 distinguishable states.