Regular expression 00 or 11 not both

Question

Can anyone help me with this question: I know it before, but I have tried to solve it myself and didnt succeed. what is the regular expression for this language: L=all words that have 00 or 11 but not both.

Thank you!

Answer 1

It will be the union of two languages: $$ A = \mbox{All words that have 00 but not 11} $$ and $$ B = \mbox{All words that have 11 but not 00} $$ A regular expression for a language that does not contain 11 can be of the form: $$(1+\epsilon)(01+0)*$$ Therefore, a regular expression for A could be: $$ (1+\epsilon)(01+0)* (00) (1+\epsilon)(01+0)* $$ And a regular expression for B could be similar.

Answer 2

Let $\Sigma=\{0,1\}$. Then $L=L'\cup L''$ where

$$L' = \{w\in\Sigma^* : w\text{ has } 00, w\text{ does not have } 11 \}, $$ $$L'' = \{w\in\Sigma^* : w\text{ has } 11, w\text{ does not have } 00 \}. $$

A regular expression for $L'$ is

$$ (0(10)^* \cup 10(10)^*)(00^*\cup 00^*10^*),$$

and a regular expression for $L''$ is

$$ (1(01)^*\cup 01(01)^*)(11^*\cup 11^*01^*). $$

Hence a regular expression for $L$ is

$$ (0(10)^* \cup 10(10)^*)(00^*\cup 00^*10^*) \cup (1(01)^*\cup 01(01)^*)(11^*\cup 11^*01^*).$$