# Regular expression at least 2 out of 3 consecutive characters should be 1

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!

• You can use this to transform a finite automaton to a regular expression. – user23039 Sep 25 '16 at 8:43
• That automaton can't be correct since it accepts all strings of length one. – Raphael Sep 25 '16 at 11:59
• 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. – user1354784 Sep 25 '16 at 15:18
• @Camil all the examples I have seen using this method seem to be limited to a single accept state. – user1354784 Sep 25 '16 at 15:24
• @Evil Sorry I forgot to specify "at least" two 1s, I will edit this right now – user1354784 Sep 25 '16 at 18:28

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:

(1|(011))*


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:

(111|011|1011|11011)


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

(|0|01)


Now all that's left is to concatenate them:

(111|011|1011|11011)(1|(011))*(|0|01)

• Thanks! We would just need to add 101|110|1101|(your expression). – user1354784 Sep 25 '16 at 20:39