COM1350 Automata Theory Spring 1998 Professor Fell
Name:
Problem 1:
(6 points)
Below are two relations on the set
R
of real numbers. For each of the relations, tell whether or not it is: reflexive, symmetric, transitive.
Explain your answers briefly.
a) x != y
That is x is related to y if and only is x
NOT equal to
y.
b)
a) x ~ y
where x ~
y if and only if xy > -1.
Problem 2:
(14 points)
a)
For the Deterministic Finite State Automaton M
and for each string shown below, show the sequence of states M
goes through on that string and tell whether or not M
accepts the string.
String
Sequence of States
Accepted / Rejected
0101
1010
1101
e
b)
Describe the language recognized by M.
Problem 3.
(60 points)
a)
Give state diagrams of DFAs recognizing the following languages. In all cases the
alphabet is {0, 1}.
b)
Give a string that is in
the language and a string that is not in
the language. For each of these strings, Show the sequence of states your DFA goes
through on that string.
i.
{ w | w is any string except 010 }
ii.
{ w | w has length at least 2 and the last two symbols in w are the same }
iii.
{ w | w contains the substring 101 }
Did you remember to do parts a and b?
Problem 4.
(20 points)
a.
Describe the language L1 recognized by M1 and the language L2 recognized by M2 below.
S = {0, 1} for both.
b.
Follow the construction of the proof of Theorem 1.12 (The class of regular languages
is closed under the union operation.) to create a DFA that recognizes
L1 union L2. You do not need to complete part a to do this.
Last Updated: May 5, 1997 10:06 pm by
Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is:
http://www.ccs.neu.edu/home/fell/COM1350/test1.html
