Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Feb 3 '13 at 8:20

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

1  
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 Satish Teli Feb 3 '13 at 19:12
add comment

2 Answers 2

up vote 2 down vote accepted

@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^*$
share|improve this answer
    
:please edit your solution // i think it should be 1^n 1^* (01^m)^*∣1∗ for the case m<n.. –  Jay Satish 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
add comment

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)^? $$
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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