How can I build a regular expression that, using only the concatenate, union and star operations, over the alphabet {0,1}, describes the language "Every three consecutive characters contain at least two 1, and the input has length at least 3"? For instance 110011, 0101 and 11 should be refused. I was thinking on using the logic from this (incomplete) DFA, but I can't figure out how to get a regular expression that follows the rule. Thanks! enter image description here

  • 1
    $\begingroup$ You can use this to transform a finite automaton to a regular expression. $\endgroup$
    – user23039
    Sep 25, 2016 at 8:43
  • $\begingroup$ That automaton can't be correct since it accepts all strings of length one. $\endgroup$
    – Raphael
    Sep 25, 2016 at 11:59
  • $\begingroup$ That's why I stated it was incomplete, I ommited the successive transitions from the initial state that lead to one of the four states above. I just wanted to show the behaviour the regulard expression should have once it reaches that point. $\endgroup$ Sep 25, 2016 at 15:18
  • $\begingroup$ @Camil all the examples I have seen using this method seem to be limited to a single accept state. $\endgroup$ Sep 25, 2016 at 15:24
  • 1
    $\begingroup$ @Evil Sorry I forgot to specify "at least" two 1s, I will edit this right now $\endgroup$ Sep 25, 2016 at 18:28

1 Answer 1


Assume that string $s$ is in $L$. We will look at the last two characters of the string:

  • 00, impossible, because this string could not be in $L$.
  • 01, next character must be 1, new last two characters is 11.
  • 10, next character must be 1, new last two characters is 01.
  • 11, next character may be 1 or 0, new last two characters is 10 or 11.

Note that no matter your current state, you will always pass through the 11 state within two steps. Assuming that $s$ ended with 11, we get the following loop:


This will be the middle section of any string in $L$. All we need to do now is handle possible prefixes, making sure not to allow any with size < 3:


And finally, possible suffixes (note the empty union to express that the suffix is optional):


Now all that's left is to concatenate them:

  • $\begingroup$ Thanks! We would just need to add 101|110|1101|(your expression). $\endgroup$ Sep 25, 2016 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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