Question $2$

Let $L=\{\begin{array}{ccc}(\text{:}{A}_1,& \text{d}\text{o}\text{t}\text{s}\text{,}& A_k\text{:})\text{:}{A}_1\\ \text{d}\text{o}\text{t}\text{s}\\ A_k\end{array}$ be DFAs over the same alphabet $$ and $.$

Prove that Lin PSPACE. You can use the fact that PSPACE $=$ NPSPACE that will be proved next

lecture.$($Actually$,L$ is PSPACE$-$Complete, but that is beyond the scope of an exercise$).$

Question $3$

The language $AL{L}_{\text{N}\text{F}\text{A}}=\{\begin{array}{c}(\text{:}A\text{:})\text{:}A\end{array}$ is an NFA and $\{$:$L(A)={}^{*}\}$ is known to be PSPACE$-$Complete. Use

this fact in order to prove that the language

$MI{N}_{\text{N}\text{F}\text{A}}=\{($:$A,k$:$)$ : there exists $an$ NFA $B$ with $L(B)=L(A)$ and $B$ has $at$ most $k$ states $\}$

is also PSPACE$-$Complete.

Question $4$:

For each of the following statements either prove, disprove, or show that it is equivalent to an open

problem:

TQBF can be solved in polynomial time by an NTM$.$

ExPTIME$=$SPACE$(n).$