[an error occurred while processing this directive]
MTH210

Tutorial 7


[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.
 p. 744 #6. Also give a regular expression in each case.

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

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

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

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

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

(ε  a  ba  bb)(a  b)^{*}

(a^{*}b)^{*}

(a^{*}b^{*})^{*}
This page is maintained by Peter Danziger.
Last modified
Saturday, 27Feb2010 17:42:53 EST