Question

Let is a regular expression with exponentiation and$\mathrm{L}\left(\mathrm{R}\right)=\varnothing$ }. Show that ${\mathrm{E}}_{\mathrm{REX}\uparrow }\in \mathrm{P}$.

Short answer

The above problem is solved by using $PSPACE\backslash \mathrm{varsubsetneq}EXSPACE$i.e., the problem of any $EXSPACE$-complete cannot be in$PSPACE$ .

Step-by-step solution

Using Regular Expressions with Exponentiation

Consider the statement is regular expression with exponentiation and $L\left(R\right)=\varnothing$

From the above statement it can be understood that R is a regular expression and the language, which contains this regular expression consists NULL values.

Applying the concept of intractability

$E_{REX\uparrow }$is said to be intractable because it can be demonstrated in such a manner that is complete for the class EXSPACE.

From the above statements we can conclude that “any EXSPACE-complete problem cannot be in PSPACE and it is much less in P”.

Because PSPACE will be same as EXSPACE which is contradicting the corollary discussed above.

Hence, it can be said that $E_{REX\uparrow }\in P$