Consider the operator $\texttt{FirstMatch} : 2^{\Sigma^*} \to 2^{\Sigma^*}$ defined as follows:

$$\texttt{FirstMatch}(L) = \left \{ y \mid y \in L, \forall \text{ prefixes } x \text{ of } y, x \not \in L \right \}$$

What is the complexity of matching regular expressions with this operator? (i.e, regular expressions with union, concatenation, Kleene iteration and FirstMatch)

Does this operator make regular expressions more succinct? Can the FirstMatch operator be applied on NFAs (without determinization)?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.