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! 
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ You can use this to transform a finite automaton to a regular expression. $\endgroup$– user23039Sep 25, 2016 at 8:43
-
$\begingroup$ That automaton can't be correct since it accepts all strings of length one. $\endgroup$– RaphaelSep 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$– user1354784Sep 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$– user1354784Sep 25, 2016 at 15:24
-
1$\begingroup$ @Evil Sorry I forgot to specify "at least" two 1s, I will edit this right now $\endgroup$– user1354784Sep 25, 2016 at 18:28
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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 is11.10, next character must be 1, new last two characters is01.11, next character may be 1 or 0, new last two characters is10or11.
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)
-
$\begingroup$ Thanks! We would just need to add 101|110|1101|(your expression). $\endgroup$ Sep 25, 2016 at 20:39