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.
Solution.
1. The set of strings containing bitstrings 10, 0010, or 0
Start S1 S2 S3
0
0
1
0
1
2.
S0 S1 S3 S2
S4
Start
1
1
1
0
1
0
0
0
0, 1
1
Regular Expression: (1 + (01)∗
)(01)∗
(1 + λ)
∗
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.
Solution.
2
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 }
Solution.
1. Yes it is a equivalence relation
2. Yes it is a equivalence relation
3. Not transitive ∀a, b, c(((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R) because if a has a common parent with b
and b has a common parent with c, it does not follow that a and c have a common parent.
4. Not reflexive ∀a((a, a) ∈ R, cannot meet yourself. Also not transitive, ∀a, b, c(((a, b) ∈ R ∧ (b, c) ∈
R) → (a, c) ∈ R)
5. Not transitive ∀a, b, c(((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R). If a and b speaks English and b and c
speak French, it does not follow that a speaks French.
3
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.
Solution.
A poset S is reflexive, transitive, and antisymmetric.
Reflexive ∀a((a, a) ∈ R
Symmetric ∀a, b((a, b) ∈ R → (b, a) ∈ R)
Antisymetric ∀a, b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b))
1. Yes = is a poset
2. Yes ≤ is a poset
3. No > is not a poset
It is not antisymmetric ∀a, b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b))
If a > b, b > a it does not follow that a = b because a > b would be false
4. No 6= is not a poset
It is not antisymmetric ∀a, b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b))
If a 6= b, it does not follow that a = b
5. No because it is not Symmetric ∀a, b((a, b) ∈ R → (b, a) ∈ R) in all cases
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist: Did you…
1. abide by the Aggie Honor Code?
2. solve all problems?
3. start a new page for each problem?
4. show your work clearly?
5. type your solution?
6. submit a PDF to eCampus?
4
Powered by TCPDF (www.tcpdf.org)
