TWiki> CS301 Web>Syllabus>Homeworks>ProblemSet3 (revision 3)EditAttach

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 2, 2012 at 10:50 AM sharp.

1 DFA

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

1. L = \{ w \in \{0, 1\}^*:\: w contains at least one 0 and exactly two 1's \}.
2. L = \{w \in \{0,1\}^* : \: w the number of 1's in w \bmod 4 = 0 \}.
3. The set of all strings with at most two substrings of 000's.
4. The set of all strings that start or end with 01.
5. The set of all strings with at least 3 0's and at most 2 1's.
6. The set of all strings in which the di fference between the number of 1's and number of 0's in any prefi x is within the range [-2,2].
7. 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):

1. The set of strings of 0's and 1's such that any two 0's separated by a number of positions that is a multiple of 3.
2. Construct an NFA with no more than 5 states for L = \{ 0101^n : n \geq 0 \} \cup \{ 010^n : n \geq 0\}.
3. Construct an NFA for the language speci ed 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)

Describe in English, as briefly as possible, the language described by each of these regular expressions:
1. (1 \cup 10) (0 \cup 1)^* (01 \cup 0)
2. (((0^* 1^*)^* 01) \cup ((0^*1^*)^*10))(1 \cup 0)^*

6 Regular expression writing

Give a regular expression to describe each language:
1. \{ w \in \{0,1\}^* : w \mbox{ does not end in } 10\}
2. \{ w \in \{0,1\}^* : w \mbox{ has 110 as a substring}\}
3. \{ w \in \{0,1\}^* : w \mbox{ does not have 110 as a substring} \}
4. \{ w \in \{0,1\}^* : w \mbox{ has both 00 and 11 as substrings}\}
5. \{ w \in \{0,1\}^* : w \mbox{ has both 11 and 101 as substrings} \}
6. Strings over 0 and 1 whose length is a multiple of 3.
7. 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:

1. Set complement.
2. Set difference.
3. Prefix: pref(L) = \{ s: \exists x \in \Sigma^* sx \in L \}
4. Suffix: suff(L) = \{ s: \exists x \in \Sigma^* xs \in L \}
5. 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^*

Edit | Attach | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r3 - 2012-01-27 - 16:33:10 - Main.sloan

 Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu WISESTHelping Women Faculty AdvanceFunded by NSF