# Asked to write a regular expression for a language but I am confused about the teachers given solution. (all strings NOT ending in 01)

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

$$\bullet$$ all strings not ending in 01.

The solution my teacher gave is

(0+1)$$^{*}$$(00+10+11)+0+1+$$\lambda$$

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.

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

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).
• 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. Oct 25, 2022 at 3:00
• @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? Oct 25, 2022 at 17:37
• @Ether Please read the definition of a regular expression again. $+$ is a symbol corresponding to an union, not a concatenation. Oct 25, 2022 at 17:39
• @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. Oct 26, 2022 at 21:12