I've been playing around with converting regular languages to regular expressions and was wondering if my thinking is correct for this one.


The set of all strings that begin or end with a doubled digit, either 11 or 00. (In all cases assume the alphabet is {0,1}).

So far, I have: $((11+00) + (1 + 0)^*) + ((1+0)^*(11 + 00))$.

My thinking is that we want to take the union of: the set of strings that start with 11 or 00 followed by any sequence of 1's and 0's AND the set of strings that end with 11 or 00 preceded by any sequence of 1's and 0's.

Sorry for the somewhat clunky writing.....still trying to get the hang of styling my questions.

  • $\begingroup$ This simplifies to $(1 + 0)^*$, as Im sure you've realised by now. And you should accept the answer, I think. $\endgroup$ – Thumbnail Apr 24 '17 at 14:28

You are thinking correctly but a small error is there in writing the regular expression. The regular expression is $r = ((00+11)(0+1)^*)+((0+1)^*(00+11))$.

| cite | improve this answer | |
  • $\begingroup$ Whoops. My mistake...didn't mean to put that extra (+). And great! Just wanted to make sure. Thank you. $\endgroup$ – Phoenixdeath Feb 22 '17 at 6:30

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.