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.

• Why is this interesting for you? What have you tried?
– Raphael
Feb 3, 2013 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.... Feb 3, 2013 at 19:12

2 Answers

@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.. Feb 4, 2013 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). Feb 4, 2013 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)^?$$