Union-free regular languages, defined by regular expressions (using $*$, literals (alphabet symbols), and concatenation) excluding union (written $+$ or $\cup$) have been studied.

Note that unions under a Kleene $*$ can always be eliminated: $$(u+v)^*=(u^*v^*)^*.$$ Now, my question is about

(preferably union-free) languages that can be defined by a regular expression not containing any subexpression of the form $u^*v^*$.

As an example, $0^*1^*$ is union-free (clearly) but I don't think it can be written without something of the form $u^*v^*$.

Have such languages been studied?

  • 1
    $\begingroup$ $u^*v^*=u^*+u^*vv^*$, so you can rewrite any regular expression not to have any subexpressions of this form. $\endgroup$ Jul 11, 2023 at 7:45
  • $\begingroup$ @EmilJeřábek Nice, this shows that we must restrict attention to the union-free case. $\endgroup$ Jul 11, 2023 at 8:04


Your Answer

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