CSE 237, Homework 1: Regular Expressions
due Wednesday 9/13/17 at the beginning of class

Please hand in the homework ON PAPER, either handwritten or printed.


Problem 1.

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

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

Remember: If there are multiple regular expressions to do the job, simpler ones are preferable.

Problem 2.

For each of the REs below, find the shortest string in the corresponding language that is not in the language of the other two REs, and explain in the simplest way possible why itís not in the other two.

(a) R1 = (bb U b)* U (ba U a)*
(b) R2 = (ba)* (ab)*

(c) R3 = (ab U aba)*a*

Example: ďaĒ is not in L2 because all string in L2 have even length.

Problem 3.

Are the following statements true or false?

In each case, justify your answer, using the appropriate definitions of strings, sets, languages, regular operations, etc
Be as precise and brief as possible.

(a)    the union of 0*1* and 1*0* equals (1 U 0)* (0 U 1)*

(b)   the intersection of 0*1 and 10* is empty

(c)    abcd is in (a (cd)* b)*

Problem 4.

For the languages (b) and (c) in Problem 1, find the FSA that accepts it. Try to make it as simple as possible.

Show your FSA both as a diagram and as a table.