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:

  1. If there are any strings which are not in the language which the regular expression generates, find one.
  2. If there are any strings which are in the language which the regular expression does not generate, find one.
  3. 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.
  1. 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*)*

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

  3. 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 Ø *))

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