<p><a href="https://cstheory.stackexchange.com/a/8156/1993">Union-free regular languages</a>, defined by regular expressions (using <span class="math-container">$*$</span>, literals (alphabet symbols), and concatenation) excluding union (written <span class="math-container">$+$</span> or <span class="math-container">$\cup$</span>) have been studied.</p>
<p>Note that unions under a Kleene <span class="math-container">$*$</span> can always be eliminated:
<span class="math-container">$$(u+v)^*=(u^*v^*)^*.$$</span>
Now, my question is about</p>
<blockquote>
<p>(preferably union-free) languages that can be defined by a regular expression not containing any subexpression of the form <span class="math-container">$u^*v^*$</span>.</p>
</blockquote>
<p>As an example, <span class="math-container">$0^*1^*$</span> is union-free (clearly) but I don't think it can be written without something of the form <span class="math-container">$u^*v^*$</span>.</p>
<p>Have such languages been studied?</p>

CC BY-SA 4.0
2023-07-11T07:45:27.487Z
$u^*v^*=u^*+u^*vv^*$, so you can rewrite any regular expression not to have any subexpressions of this form.
Emil Jeřábek
CC BY-SA 4.0
2023-07-11T08:04:58.230Z
@EmilJeřábek Nice, this shows that we must restrict attention to the union-free case.
Bjørn Kjos-Hanssen
<regular-language><regular-expressions>
Languages free of concatenations of stars
Bjørn Kjos-Hanssen
# Languages free of concatenations of stars

(Asked by: username_0 on 2023-07-11)

[Union-free regular languages](https://cstheory.stackexchange.com/a/8156/1993), 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?

**Tags:** regular-language, regular-expressions

> **Comments:**
> **username_1**: $u^*v^*=u^*+u^*vv^*$, so you can rewrite any regular expression not to have any subexpressions of this form.  
> **username_0**: @EmilJeřábek Nice, this shows that we must restrict attention to the union-free case.  

---

## 0 answers

