-1

Can anyone help me with this question: I know i asked a similar question not a while ago but i'm not able to understand how its possible. If anyone could give me a lot of examples instead of an answer.

I need to find the regular expression for this language: L=all words that have 00 or 11 but not both.

Thank you!

draanb
  • 3
  • 1
    You asked a similar question an hour ago. Are you perhaps expecting people to do your homework? I suggest elaborating on where you are stuck. – Roy Nov 22 '14 at 15:05
  • I know..hh But i just dont know how to do this when one thing depends on the other. Like this when 00 or 11 can be but not both. 00 i can do, 11 i can do, both i can do, but as described in my question i dont understand how its possible – draanb Nov 22 '14 at 15:12
  • Can you find a regular expression for words that contain 00 but do not contain 11? – Matt Nov 22 '14 at 15:51
  • I think so : (01+001)+1(01+001) – draanb Nov 22 '14 at 15:56

1 Answers1

0

Here is my hint. Build a finite state machine to accept this language. So we start at $q_{0}$. If we read in a $0$, go to state $q_{1}$. Otherwise, go to state $q_{2}$.

At $q_{1}$, if we read in a $1$, go to $q_{0}$. Otherwise, go to $q_{3}$. From $q_{3}$, the idea is that if you read in a $11$, reject. So you can build the state transitions from there. The idea is similar branching out from $q_{2}$, except we check if we've read in a $11$, then check that we don't read in a $00$.

Then you can use a method to convert a FSM to a regular expression, using something like state reduction or the Brzozowski Algebraic Method.

ml0105
  • 14,674