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 three 0's
(c) All strings with exactly one occurrence of the substring 10

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) R1 = (ab U aba)*a*
(b) R2 = (bb
U b)* U (ba U a)*
(c) R3 = (ba)* (ab)*

Example: "a" is not in L3 because all string in L3 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.