MTH210	Tutorial 7
	Regular Expressions

Readings

The first few questions in each tutorial set are generally easier. Make sure that you do some of the more challenging problems as these will be closer to the level of the quiz questions.

Your TA will take up some of these questions in class. However, there will not usually be time to cover all the assigned questions. You may ask your TA about any of the assigned problems if you have questions.

You may also be asked to work on problems during the tutorial. Only students who work diligently on the assigned material will receive the attendance mark.

Tutorial 7

1. p. 744 #6. Also give a regular expression in each case.

2. Find regular expressions for the following languages over {0, 1}:

   1. {x ∈ {0, 1} | x contains the string 1101 }

   2. {x ∈ {0, 1} | x is of even length } (contains an even number of characters)

   3. {x ∈ {0, 1} | x is contains an odd number of 1's }
      (Note that we did even # of 1s in class.)

3. Each of the following regular expressions denotes a language over the alphabet Σ = {a, b}. In each case give the following:
   1. State whether ε is in the language.
   2. Where possible give 2 strings which are in L and two strings which are in Σ^*, but not in L.
   3. Describe the language as succinctly as possible in words, using as few symbols as you possibly can.
   1. (ε | a | ba | bb)(a | b)^*
   2. (a^*b)^*
   3. (a^*b^*)^*