Call a regular expression star-freeif it does not contain any star operations.Then,let

$E{Q}_{\mathrm{SF}-\mathrm{REX}}=\left\{(\mathrm{R},\mathrm{S})|\mathrm{R}\mathrm{and}\mathrm{S}\mathrm{are}\mathrm{equivalent}\mathrm{star}-\mathrm{free}\mathrm{regular}\mathrm{expressions}\right\}$. Show that$E{Q}_{\mathbf{SF}-\mathbf{REX}}$ is in coNP. Why does your argument fail for general regular expressions?

To show that the language is in NP, there should be a Nondeterministic turning machine NTM that recognize the language in polynomial time.

Let's say string x inis in the following form:

• X is not a viable representation of two regular languages.
• Although X is of the acceptable form (R,S), neither R nor S, nor both, are star-free.
• R and S are both star-free, but$L\left(R\right)\ne L\left(S\right)$then X is of the valid form (R,S).

So If x is in the first and second forms, a DTM can accept it in polynomial time. If x is in the third form, then y must be in one of the L(R) or L(L) forms (S). The length of y is polynomial in the size of |R|+|S| when R and S are star-free and $L\left(R\right)=L\left(S\right)$As a result, an NTM exists.

It can be fail in general regular language because there is no such type of string accepted by the language.