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