**CSE
237, Homework 1: Regular Expressions**

**due Tuesday 1/30/17** **at the beginning of class**

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

**Problem 1. **

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

(a)All strings whose length is divisible by three

(b)All strings with no more than three0's

(c)All strings with exactly one occurrence of the substring10

**Problem 2.**

For *each* of the REs below, find a 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}=(abUaba)*a*

(b)R_{2}=(bbUb)*U(baUa)*

(c)R_{3}=(ba)* (ab)*

Example: "a" is not
in L_{3} because all string in L_{3} have even length.

**Problem 3.**

Are the following
statements true or false? In each case,* justify your answer, making use of
the appropriate definitions of strings, sets, languages, regular operations, *etc

Be as precise and brief as possible.

(a) *adbc* is in **(a (b ****U**** c)* d)***

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

**Problem 4.**

For the three languages in Problem 1, draw the diagram for the DFA (Deterministic Finite State Automaton) that recognizes it.