0

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!

draanb
  • 3
  • 1
    Did you try constructing a DFA to recognize this language? That should help. – Math1000 Nov 25 '14 at 12:08
  • I constructed the dfa of the language that have 00, another dfa for the language that contain 11, using both i constructed the language that contain 11 or 00 but not both. I tried converting that dfa to regular expression but it didnt work for me..maybe i did somthing wrong – draanb Nov 25 '14 at 12:12

2 Answers2

0

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.

Mario Román
  • 353
0

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^*).$$

Math1000
  • 36,983
  • Thank you too for your answer, im sorry that i cant accept two answers but he commented first, and so i read his answer first – draanb Nov 25 '14 at 12:31