PROBLEM SET 1, CSC 280, 2006
DUE BEFORE CLASS, WED. FEB. 1
The first problem set is as follows (I will shortly place this on the
course web site as well). All 10 problems will be marked out of the same
total. Answers to any 7 questions make a complete answer paper. However,
you can do all questions to earn bonus points (i.e., you can in principle
obtain "more than 100%" on the assignment.
Reminder: The problems are expected to be done by you alone, without direct
~~~~~~~~ outside or collaborative help (but you may certainly discuss
the general principles involved with others; and the TAs may
sometimes provide help to the class as a whole, in recitations
or on the web site, at their discretion); see web site or notes
handed out previously for details about collaboration.
Keep your eyes on the instructor's and the TAs' web site for any corrections
or discussion.
PROBLEM 1
~~~~~~~~~
On pp. 46-7, Sipser sketches a proof that the regular languages are
closed under union. (This was also briefly covered in class, though
not in the overhead lecture notes.) He indicates that a more formal proof
would include an inductive proof that the construction of the "union
machine" M really works. Provide such a proof; i.e., for the basis,
show that M works correctly for "short" strings, then assume for induction
that it works correctly for strings of length k (i.e., such a string will
take M to an accepting state iff it takes either M1 or M2 to an accepting
state), and prove that it works correctly for strings of length k+1.
(Hint: Think of this in terms of the particular state that is reached
in M by a particular string of length k, and then think about the
conditions under which a particular additional symbol takes M to an
accepting or non-accepting state.)
PROBLEM 2
~~~~~~~~~
a. Can we always convert a DFA with multiple accepting states to a DFA
with one accepting state? Why or why not? Justify your answer in detail.
b. Give the state diagram of a 6-state DFA for the language L of strings
over {a,b} where each string consists of 2 a's followed by 0 or more b's,
or 2 b's followed by 0 or more a's. (Hint: first construct a state
diagram that ignores edges that cannot lead to an accepting state.
Then add a single state that all the ignored edges lead to.)
c. For the language L in (b), consider L*. Give a BRIEF English
(non-symbolic) characterization of this expanded language, and
give the state diagram of a DFA recognizing it. (Unnecessarily
complex answers will lose marks.)
d. A DFA is obviously a special case of an NFA, if one views both kinds
of automata in terms of their state graphs (as we commonly do, when
not being absolutely formal): a DFA just lacks epsilon-edges and
has exactly one edge exiting from each state for each symbol in
the assumed alphabet, labeled with that symbol.
However, from the perspective of our formal tuple/set-theory based
definition of the 2 kinds of automata, no DFA is (strictly) an NFA.
State what the differences are that prevent formal identity of any
DFA with any NFA.
PROBLEM 3
~~~~~~~~~
Sipser Exercise 1.14.
PROBLEM 4
~~~~~~~~~
Sisper Exercises 1.4(a,c), 1.5(c,e), 1.6(b,d).
PROBLEM 5
~~~~~~~~~
Sipser Exercises 1.7(b,c,e)
PROBLEM 6
~~~~~~~~~
Consider the NFA in example 1.33 in the text (p. 52). Convert this NFA to
an equivalent DFA (showing the state diagram), by using the ideas in the
proof of Theorem 1.39.
PROBLEM 7
~~~~~~~~~
a. Complete the following statements by supplying a suitable condition on
L(R), where R is a regular expression and e is the empty-string symbol:
i. L(R U e) = L(R) iff ...
ii. L(R ° Ø) = L(R) iff ...
Briefly justify your answers.
b. Let's call a string that contains at least one a and at least one b an
"ab-string". For the languages determined by each of the following regular
expressions (where E+ is an abbreviation for EE*), give 2 ab-strings of
length at least 4 that are in the language, and 2 ab-strings of length
at most 4 that are not in the language (so, 4 strings per language):
i. (a(abb)* U b)
ii. (a+ U (ab)+)
iii. (a U b+)a+b+
c. Give regular expressions for the languages of Sipser Exercise 1.6(b,d,f)
PROBLEM 8
~~~~~~~~~
Sipser Exercise 1.12
PROBLEM 9
~~~~~~~~~
Convert the regular expression (ab* U ba*)* to an NFA, using the conversion
procedure that was the basis of the proof that for any regular expression
R there is an NFA N such that L(N) = L(R). Show intermediate stages in
the construction.
PROBLEM 10
~~~~~~~~~~
Sipser Problem 1.41