CSE 237, Homework 1: Regular Expressions
due 2/1/06 in class

1.Please start each problem on a new sheet.

2. Note: you may find it easier to work on the problems in a different order.

Problem 1.

Let S = {a,b}.  Write regular expressions (REs) for the following languages over S:

(a) All strings with a number of a's divisible by two
(b) All strings with no more than four b's
(c) All strings with exactly one occurrence of the substring aba

Problem 2.

For each of the REs below, find 2 strings in the corresponding language that are not in the language of the other two REs:

(a) R₁ = (01 U 010)*0*
(b) R₂ = (11 U 1)* U (10 U 0)*
(c) R₃ = (10)* (01)*

Problem 3.

Which of the following statements about languages described by regular expressions are true?
In each case, prove or disprove the statement.

(a) abb is in a*b*a*
(b) abcc is in (a (cc)* b)*
(c) the union of ab* and ba* equals ba* U ab*
(d) the intersection of a*b* and a*b* is empty

Note: we treat regular expressions as stand-ins for the language they specify.