ProblemSet3 < CS301

CS301 Web>Syllabus>Homeworks>ProblemSet3 (2012-01-31, Main.ctanti2) (raw view)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. <br />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):*

   1 <latex>L = \{ w \in \{0, 1\}^*:\: w</latex> contains at least one 0 and exactly two 1's <latex> \}. </latex>
   1 <latex>L = \{w \in \{0,1\}^* : \: w </latex> the number of 1's in <latex> w \bmod 4 = 0 \}. </latex>
   1 The set of all strings with at most two substrings of _000's_.
   1 The set of all strings that start or end with _01_.
   1 The set of all strings with at least 3 _0's_ and at most 2 _1's_.
   1 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].
   1 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 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.)
   1 Construct an NFA with no more than 5 states for <latex>L = \{ 0101^n : n \geq 0 \} \cup \{ 010^n : n \geq 0\}.</latex>
   1 Construct an NFA for the language specied by the regular expression: <latex>(10 \cup 11)^* \cup (01 \cup 00)^*. </latex>
---++++ 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 <latex> \varepsilon \in L(M) </latex> 
---++++ 5 Regular experssion understanding
 Describe in English, as briefly as possible, the language described by each of these regular expressions: 
   1 <latex> (1 \cup 10) (0 \cup 1)^* (01 \cup 0) </latex>
   1 <latex> (((0^* 1^*)^* 01) \cup ((0^*1^*)^*10))(1 \cup 0)^*</latex>
---++++ 6 Regular expression writing
 Give a regular expression to describe each language: 
   1 <latex> \{ w \in \{0,1\}^* : w \mbox{ does not end in } 10\} </latex>
   1 <latex> \{ w \in \{0,1\}^* : w \mbox{ has 110 as a substring}\}</latex>
   1 <latex> \{ w \in \{0,1\}^* : w \mbox{ does not have 110 as a substring} \}</latex>
   1 <latex> \{ w \in \{0,1\}^* : w \mbox{ has both 00 and 11 as substrings}\}</latex>
   1 <latex> \{ w \in \{0,1\}^* : w \mbox{ has both 11 and 101 as substrings} \}</latex>
   1 Strings over 0 and 1 whose length is a multiple of 3.
   1 Strings over 0 and 1 containing at most three 0's.
---++++ 7 Simplify as much as you can:
 <latex> (0 \cup 1)^* (1 \cup \varepsilon)^* 0^*</latex> 
---++++ 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.
   1 Set difference.
   1 Prefix: <latex> pref(L) = \{ s: \exists x \in \Sigma^* sx \in L \} </latex>
   1 Suffix: <latex> suff(L) = \{ s: \exists x \in \Sigma^* xs \in L \} </latex>
   1 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 <latex> \setminus </latex>. <latex> S \setminus T </latex> 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:

<latex> (0 ( 0 \cup \varepsilon) 0 )^* </latex>

<latex> 010 \cup 1^* </latex>

<u> <br /> </u>
Topic revision: r5 - 2012-01-31 - 23:28:32 - Main.ctanti2
CS301
[edit this menu]
WISEST
Helping Women Faculty Advance
Funded by NSF