I need help for this exercise of regural expression


To solve this exercise, we need to find regular expressions for two classes of words:

  • Words of the form $ x00 $, or $ x neq epsilon $ and the only occurrence of $ 00 $ is at the end.
  • Words of the form $ x01 $, or $ x neq epsilon $ and the only occurrence of $ 01 $ is at the end.

Let's start with the first class. To begin, $ x $ must end with $ 1 $ or $ 2 $. So, these words are of one of the forms $ y100 $ or $ y200 $, or $ y $ does not contain $ 00 $. You probably already know how to describe all words that do not contain $ 00 $ using a regular expression.

For the second class, the only constraints on $ x $ are it's not empty and does not contain $ 01 $. If you do not like the "non-empty" constraint, you can use the following case distinction:

  • Yes $ x = y0 $ or $ x = y2 $, then the only constraint on $ y $ does not contain $ 01 $.
  • Yes $ x = y1 $then $ y $ can not finish with $ 0. It could be empty. If this ends with $ 2 $then $ x $ is of the form $ z21 $. If this ends with $ 1 $we are in the same situation again: the previous symbol (if any) can not be $ 0. Continuing this way, we see that either $ x in 1 ^ + $ or $ x $ is of the form $ y2z $, or $ y $ does not contain $ 01 $ and $ z = 1 ^ n $ for some people $ n geq 1 $.

I let you understand how to describe the strings $ y $ by avoiding $ 01 $ – This is very similar to the case of avoiding $ 00 $.