## 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.