Question

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?

Short answer

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

Step-by-step solution

To Recognition of language 

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

To explain the regular languages

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.