[an error occurred while processing this directive]

MTH210

Tutorial 7

Ryerson University
[an error occurred while processing this directive]

(none)

[an error occurred while processing this directive]

Regular Expressions

[an error occurred while processing this directive]

(none)

[an error occurred while processing this directive]

Due: (none)


Readings

This tutorial covers material from section 12.1 of the textbook. Page and exercise numbers are from the course textbook.

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*)*


This page is maintained by Peter Danziger.
Last modified Saturday, 27-Feb-2010 17:42:53 EST