CSC 320: Summer 2017
Tutorial #3, Tues. May 30, 1:30pm or 2:30pm
One goal of this tutorial is for you to learn to be able
to distinguish between correct and incorrect regular expressions
for a language and to justify your answers.
For each of the proposed solutions below:

If there are any strings which are not in the language
which the regular expression generates, find one.

If there are any strings which are in the language
which the regular expression does not generate, find one.

Otherwise, justify that it is a correct answer to the problem.
Each of the following languages is defined over {0,1}.
Note: I used U to mean union and also the empty set
symbol should appear as Ø which should work on
most but possibly not all browsers.
These solutions were inspired
from solutions past students submitted.

L= {w: w contains 0011}
(a)
0* 1* 0011 0* 1*
(b)
(0* 1*)* 0011 (0* 1*)*
(c)
(01)* 0011 (01)*
(d)
(0 U 1)* (00 U 11) (00 U 11) (0 U 1)*
(e)
(0* 1*)* 011 (1 0*) (1* 0*)*
(f)
(0* 1*)* 011 (1 0*) (1 0*)*

L= {w: w does not contain 01}
(a)
1*
(b)
(0 U 1)* 0*
(c)
(00 U 1)* ( 01 U Ø *) *
(d)
(11* 0* U 00* U Ø* )
(e)
(1 U Ø *) (1 U 10) *
(f)
(1 U Ø * ) ( 0 U 11)*

L= {w : w starts and ends with the same symbol, w > 0}
(a)
1 (0 U 1)* 1 U 0(1 U 0)* 0
(b)
(010)* U (101)*
(c)
(1* (0U1)* 1*) U (0* (0 U 1)* 0*)
(d)
00* U 11* U (0 (0 U 1)* 0) U (1 (0U1)* 1)
(e)
(0 U 1)* (1 U Ø * ( 0 U Ø *))

L={w: w has odd length}
(a)
(0 U 1) * (00 U 01 U 10 U 11)*
(b)
01 (10)*
(c)
(0 U 1) ((00)* U (01)* U (10)* U (11)* )
(d)
(0 U 1) ((00)* U (01)* U (10)* U (11)* )*
(e)
(0 U 1)* (00 U 01 U 10 U 11 )*