Description
Problem 1. (25 points)
1. Build a finite-state automaton that accepts the language 1∗0(1 ∪ 01∗0)∗
. Give an English description
of the language (your description should be about 10 words long, of which the first 5 are the set of
strings containing).
2. Build a finite state automaton that recognizes the set of strings that end in 11 and do not contain 00.
Convert this finite-state automaton into an equivalent regular expression.
Problem 2. (25 points)
Construct a Turing machine that recognizes the set {0
2n1
n | n ≥ 0}. The Turing machine starts with the
input on the tape and the head over the leftmost symbol of the input. The symbols to the left of the input
are blanks out to infinity, as are the symbols to the right of the input. If the string is accepted, the machine
should halt with 1 on the tape (the rest of the tape should be blank). If the string is rejected, the machine
should halt with 0 on the tape.
Note: this is not an easy task, it will take you several revisions to get it right, do not get discouraged.Problem 3. (25 points)
For each relation on the set of all people, determine whether it is an equivalence realtion. For each relation
that is not an equivalence relation, determine which properties of an equivalence relation it lacks. Your
answers are not complete unless you include the definition of each property.
1. {(a, b) | a and b are the same age }
2. {(a, b) | a and b have the same parents }
3. {(a, b) | a and b share a common parent }
4. {(a, b) | a and b have met }
5. {(a, b) | a and b speak a common language }
Problem 4. (25 points)
Which of these are partially ordered sets? For each relation whichis not a partial ordering, determine which
properties of a partial ordering the relation lacks. Your answers are not complete unless you include the
definition of each property.
1. (R, =)
2. (R, ≤)
3. (R, >)
4. (R, 6=)
5. (P(Z), ⊆), where P(·) is the powerset.
