TWiki
>
CS301 Web
>
Syllabus
>
Homeworks
>
ProblemSet3
(revision 1)
Edit
Attach
CS 301, Spring 2012, Problem Set 3
1 DFA
Construct DFA's for the following languages:
L = \{ w \in \{0, 1\}^*:\: all \: strings \: with \: at \: least \: one \: 0 \:and \: exactly \: two \: 1's \}.
L = \{w \in \{0,1\}^* : \:all\: strings \: with \: the \: number \: of \: 1's\: mod \: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 dierence between the number of
1's
and number of
0's
is 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:
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.
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)^*.
More questions to come.
Edit

Attach

P
rint version

H
istory
:
r5

r4
<
r3
<
r2
<
r1

B
acklinks

R
aw View

Raw edit

More topic actions...
Topic revision: r1  20120124  00:50:12  Main.hhabib3
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