Regular expression for binary words with few zeros

Question

What is the regular expression for the set of binary strings with the property that

1. every $0$ is followed by exactly $m$ times $1$ and
2. every $0$ is preceded by at least $n$ times $1$?

$m$ and $n$ are integers.

Answer 1

@SamM's answer isn't completely right. Yes, it is $(01^m)^*$ for "each zero is followed by exactly $m$ ones", but this can't just be combined with "at least $n$ ones before". And a string of only ones complies always. So consider the ones between two zeroes:

• If $m < n$, you can't comply with both conditions, so the language is just $1^n 1^* 0 1^m \mid 1^*$
• If $m \ge n$, the only way to comply in between zeroes is to have $m$ ones there, so the language is $1^n 1^* (0 1^m)^+ \mid 1^*$

Answer 2

Vonbrand already provided an answer for the case where the strings are defined over $\{0,1\}$. I'm considering the larger alphabet $\{0,1,2\}$ (this can easily be extended to any other alphabet, $2$ basically stands for anything but a $0$ or a $1$).

The answer still depends on $n$ and $m$

• If $m<n$, you need separators between blocks of $1^*1^n01^m$: $$(1|2)^*\quad\left(1^n01^m2(1|2)^*\right)^*\quad(1^n01^m)^?$$
• If $m>=n$, you either have a separator (and thus a new sequence of at least $n$ $1$s) or you don't: $$ (1|2)^*\quad\left(1^n\left(01^m\left(2(1|2)^*1^n\right)^?\right)^*\right)^?\quad\left(2(1|2)^*\right)^? $$