# Regular expression for binary words with few zeros

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.

## migrated from cstheory.stackexchange.comFeb 3 '13 at 8:20

This question came from our site for theoretical computer scientists and researchers in related fields.

• Why is this interesting for you? What have you tried? – Raphael Feb 3 '13 at 10:18
• Sorry .. that i didnt show what i tried ... but this question is INTERESTING for me BCOZ the same language has DIFFERENT Regulalar Expressions depending on values of m and n ....See vonbrand's answer for details.... – Jay Teli Feb 3 '13 at 19:12

@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^*$
• :please edit your solution // i think it should be 1^n 1^* (01^m)^*∣1∗ for the case m<n.. – Jay Teli Feb 4 '13 at 14:36
• @JaySatishTeli, that is the same set as mine, just that my take can generate $1^k$ only by the second option, yours can give some by the first too. De gustibus non est disputandum (if my spelling isn't way off, that is). – vonbrand Feb 4 '13 at 17:04

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)^?$$