Question

Let .$\mathit{E}{\mathit{Q}}_{\mathbf{R}\mathbf{E}\mathbf{X}}\mathbf{=}\mathbf{\left\{}\mathbf{\right(}\mathit{R}\mathbf{,}\mathit{S}\mathbf{\left)}\mathbf{\right|}\mathit{R}\mathit{a}\mathit{n}\mathit{d}\mathit{S}\mathit{a}\mathit{r}\mathit{e}\mathit{e}\mathit{q}\mathit{u}\mathit{i}\mathit{v}\mathit{a}\mathit{l}\mathit{e}\mathit{n}\mathit{t}\mathit{r}\mathit{e}\mathit{g}\mathit{u}\mathit{l}\mathit{a}\mathit{r}\mathit{e}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\mathit{s}\mathbf{\}}$Show that $\mathit{E}{\mathit{Q}}_{\mathbf{R}\mathbf{E}\mathbf{X}}\mathbf{\in }\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}$.

Short answer

The $E{Q}_{REX}\in PSPACE$is showed.

Step-by-step solution

To State the PSPACE

PSPACE is the collection of all decision problems that a Turing machine can answer using a polynomial space in computational complexity theory.

To Explain the   Nondetermininstic algorithm

The complement of $E{Q}_{REX}$can be found in $NPSPACE=PSPACE$ . PSPACE, on the other hand, is closed under complement. The accept and reject states can be exchanged to get the complement decider. Consequently, $E{Q}_{REX}\in PSPACE$

Non-determininstic algorithm to decide:

1. If the input does not encode two NFAs A and B, reject it; otherwise, set a=|A| and b=|B|.
2. Save a state list $S\subseteq Q_A\left(O\right(a\left)space\right)$, a state list $T\subseteq Q_B\left(O\right(b\left)space\right)$ , and a string length counter I that takes up linear space.
3. Set S $\in -closure$ equal to the initial state of A and T equal to the initial state of B. then set$I=0$
4. set For$I=0to{2}^{a+b}$
5. If the final state is not contained in state A but is included in state B, or vice versa, the symbols chosen thus far form a string that distinguishes A and B. Accept.
6. Choose a symbol$\sigma \in \sum$ in a nondeterministic manner.
7. Change S to be the ${\cup }_{s\in S}{\delta }_A(s,\sigma )$and T to be the same as S.

Therefore, The$E{Q}_{REX}\in PSPACE$is showed.