The problem reads as follows:

Write a regular expression for the following language on {0, 1}:

$\bullet$ all strings not ending in 01.

The solution my teacher gave is


So if I understand this correctly I could produce a string like

0001 right? Which ends in 01 which is what we DON'T want.

Can someone please explain if I've misunderstood or if the solution is actually incorrect.

Edit: Fixed the teacher's given solution so that it is accurate/correct but still looking for an explanation as to why it is correct.

  • $\begingroup$ Looks like two daft mistakes. (00+01+11) should obviously be (00+10+11). And 1* should be just 1. $\endgroup$
    – gnasher729
    Oct 25, 2022 at 11:12

1 Answer 1


It is more likely that the solution is $\underbrace{(0+1)^*(00+10+11)}_{\text{words of two or more letters not ending with }01} + \underbrace{0 + 1 + \lambda}_{\text{words of 0 or 1 letter}}$.

Notice that the $(00 + 01 + 11)$ part has been transformed into $(00 + 10+11)$. Also the Kleene star on the last $1$ is useless (since a word $1^k$ with $k\geqslant 2$ can be obtained with the first part).

  • $\begingroup$ oh yes, I accidently transposed the 1 and 0 for (00+10+11). Oops. However, I still don't get how the rest of the expression would prevent there being a string that ends in 01. The way I understand it, the first part can generate a 0 or 1 any number of times, the second part can be 00 or 10 or 11. Then the last is 0 or 1 or $\lambda$. So, that means that the second part could be 00 and the last could be 1 which results in a string ending with 01. I must be misunderstanding something, but I don't know what. $\endgroup$
    – Ether
    Oct 25, 2022 at 3:00
  • $\begingroup$ First come all the two or more letter words except those ending in 01. That leaves the empty string and the two possible one letter words. $\endgroup$
    – gnasher729
    Oct 25, 2022 at 11:13
  • $\begingroup$ @gnasher729 Let me know if I have this right, so for (0+1)^{*} that means I can choose 0 or 1, any number of times include zero times. Then for (00+10+11) I would choose only one of those. Then for the last part I would choose either 0 or 1 or $\lambda$. So let's say for the second part-- the (00+10+11) part-- I choose 00. Then for the last part I chose 1. Would that not result in a string ending in 01. It would be 001 but that is still considered to be ending in 01 right? $\endgroup$
    – Ether
    Oct 25, 2022 at 17:37
  • $\begingroup$ @Ether Please read the definition of a regular expression again. $+$ is a symbol corresponding to an union, not a concatenation. $\endgroup$
    – Nathaniel
    Oct 25, 2022 at 17:39
  • 1
    $\begingroup$ @Nathaniel okay I think I see where I messed up. I was overlooking the $+$ that comes after (00+10+11). So, it's either (00+10+11) OR 0 OR 1 OR $\lambda$. As opposed to what I was thinking which was any of the letters in parentheses AND THEN also one of the latter letters. $\endgroup$
    – Ether
    Oct 26, 2022 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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