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

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 : http://cs.stackexchange.com/questions/9442

3.2K people like this

 Download Related Notes/Documents