## CS 301, Spring 2012, Problem Set 3

###### Instructions for submission:

Construct the DFAs and NFAs for the following problems using JFLAP, and turn in your automata using the blackboard. There is a folder with the name Problem Set 3, you can attach and submit your .jff or zipped files through that.

The submission through this folder will close on February 3, 2012 at 10:50 AM sharp.

#### 1 DFA

**Construct DFA's for the following languages (please use JFLAP):**

- L = \{ w \in \{0, 1\}^*:\: w contains at least one 0 and exactly two 1's \}.
- L = \{w \in \{0,1\}^* : \: w the number of 1's in w \bmod 4 = 0 \}.
- The set of all strings with at most two substrings of
*000's*.
- The set of all strings that start or end with
*01*.
- The set of all strings with at least 3
*0's* and at most 2 *1's*.
- The set of all strings in which the difference between the number of
*1's* and number of *0's* in any prefix is within the range [-2,2].
- The set of all strings of the form
*11x*, where *x* contains an even number of 0's.

#### 2 NFA

**Construct NFA's for the following languages (please use JFLAP):**

- The set of strings of
*0's* and *1's* such that there are two *0's* separated by a number of characters that is a multiple of 3. (Remembmer that 0 is a multiple of 3.)
- Construct an NFA with no more than 5 states for L = \{ 0101^n : n \geq 0 \} \cup \{ 010^n : n \geq 0\}.
- Construct an NFA for the language specied by the regular expression: (10 \cup 11)^* \cup (01 \cup 00)^*.

#### 3 NFA to DFA conversion

Please do problems 1.16 (a) and (b) from the Sipser textbook on paper and turn in the paper. I strongly suggest that you do these problems on paper first, and either do not use JFLAP at all, or use it only after to check your work. There will be a problem like this that you must do by hand on the midterm.

#### 4 Short and easy

What simple property must a DFA M have if

\varepsilon \in L(M)
#### 5 Regular experssion understanding

Describe in English, as briefly as possible, the language described by each of these regular expressions:

- (1 \cup 10) (0 \cup 1)^* (01 \cup 0)
- (((0^* 1^*)^* 01) \cup ((0^*1^*)^*10))(1 \cup 0)^*

#### 6 Regular expression writing

Give a regular expression to describe each language:

- \{ w \in \{0,1\}^* : w \mbox{ does not end in } 10\}
- \{ w \in \{0,1\}^* : w \mbox{ has 110 as a substring}\}
- \{ w \in \{0,1\}^* : w \mbox{ does not have 110 as a substring} \}
- \{ w \in \{0,1\}^* : w \mbox{ has both 00 and 11 as substrings}\}
- \{ w \in \{0,1\}^* : w \mbox{ has both 11 and 101 as substrings} \}
- Strings over 0 and 1 whose length is a multiple of 3.
- Strings over 0 and 1 containing at most three 0's.

#### 7 Simplify as much as you can:

(0 \cup 1)^* (1 \cup \varepsilon)^* 0^*
#### 8 Closure

You will probably do all of these by constructions on DFAs and/or NFAs; the first two must be done by such construction.

Prove that the regular languages are closed under:

- Set complement.
- Set difference.
- Prefix: pref(L) = \{ s: \exists x \in \Sigma^* sx \in L \}
- Suffix: suff(L) = \{ s: \exists x \in \Sigma^* xs \in L \}
- Reverse (the set of all the strings reversed)

Review/reminder: Complement is a unary operation on sets. The complement of Set S is everything not in Set S. Difference is a binary operator on sets denoted by

\setminus .

S \setminus T is the set of all things that are in S but not in T.

#### 9 Conversion of FA to regular expressions

Do Sipser textbook exercise 1.21 (a) and (b) with pencil and paper. Again, this is a construction you will probably have to carry out on the midterm and/or final.

#### 10 Conversion of regular expressions to FA

Converst both of the following regular expressions to finite automata using the procedure described in Lemma 1.55 of the text and covered in class:

(0 ( 0 \cup \varepsilon) 0 )^*

010 \cup 1^*

__ __