Cheap and Secure Web Hosting Provider : See Now

[Solved]: Regular expression for binary words with few zeros

, , No Comments
Problem Detail: 

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.

Asked By : Jay Teli

Answered By : vonbrand

@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^*$
Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback