Q$2.1$

Select all and only the languages below for which $L^{**}=L.$

Q$2\mathrm{.}2$

$1$ Point

True or False: The construction from Theorem $1\mathrm{.}49$ for an NFA that recognizes $L^{**}$ from an NFA that

recognizes $L$ always gives the smallest number of states required in an NFA that recognizes $L^{**}.$

True

False

Q$3$ NFA to DFA

$2$ Points

Consider the following state diagram of a NFA over the alphabet $\{a,b\}.$

Answer the following questions about applying the construction for building an equivalent DFA

from Theorem $1\mathrm{.}39.$

What is the start state of the equivalent DFA?

$q0$

$,\{q0\}$

$\{q0,q,n\}$

What is the output of the transition function for the equivalent DFA from the start state on reading

the character $a?$

$1\frac{O}{?}$

$\{q0\}$

$\{q\}$

$\{n\}$

$\{q,n\}$

$\{q,d\}$

$\{r,n\}$

$\{r,d\}$

None of the above, because DFA have a single state as the output of each transition function

application, not a set of states.