4
$\begingroup$

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

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

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)
$\endgroup$
  • $\begingroup$ Thanks! We would just need to add 101|110|1101|(your expression). $\endgroup$ – user1354784 Sep 25 '16 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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