TWiki
>
CS301 Web
>
Syllabus
>
Homeworks
>
ProblemSet3
(2012-01-31, Main.ctanti2)
(raw view)
E
dit
A
ttach
---++ 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>
E
dit
|
A
ttach
|
P
rint version
|
H
istory
: r5
<
r4
<
r3
<
r2
<
r1
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r5 - 2012-01-31 - 23:28:32 - Main.ctanti2
CS301
Syllabus
Homeworks
Reading Assignments
Discussion Board
Additional Material
[edit this menu
]
Log In
CS301 Web
Create New Topic
Index
Search
Changes
Notifications
RSS Feed
Statistics
Preferences
ABOUT US
Our Department
Recent News
Contact Us
ACADEMICS
Prospective Students
Undergraduate
CS Minor
Graduate
Courses
RESEARCH
Overview
By Faculty
Labs
PEOPLE
Faculty
Adjuncts
Staff
Students
Alumni
Copyright 2016 The Board of Trustees
of the University of Illinois.
webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF