**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)R_{1}=(bbUb)*U(baUa)*

(b)R_{2}=(ba)* (ab)*

(c)R_{3}=(abUaba)*a*

Example: “a” is not in L_{2}
because all string in L_{2} 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*.