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.

  • 1
    $\begingroup$ Why is this interesting for you? What have you tried? $\endgroup$ – Raphael Feb 3 '13 at 10:18
  • $\begingroup$ 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.... $\endgroup$ – 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^*$
  • $\begingroup$ :please edit your solution // i think it should be 1^n 1^* (01^m)^*∣1∗ for the case m<n.. $\endgroup$ – Jay Teli Feb 4 '13 at 14:36
  • $\begingroup$ @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). $\endgroup$ – 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)^? $$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.