COMP 330 Autumn 2018
Assignment 1
Solutions
Prakash Panangaden
Question 1[20 points] Fix a finite alphabet Σ and let ∅ 6= L ⊆ Σ∗. We define the following relation
R on words from Σ∗:
∀x, y ∈ Σ∗, xRy if ∀z ∈ Σ∗, xz ∈ L iff yz ∈ L.
Prove that this is an equivalence relation.
Solution. We must check the three properties:
reflexivity: We want to show ∀x ∈ Σ∗, xRx. This means that ∀z ∈ Σ∗, xz ∈ L iff xz ∈ L; this is clearly
true since the two sides of the “iff” are exactly the same.
symmetry: Here we want to show that ∀x, y ∈ Σ∗, xRy implies yRx.
∀z ∈ Σ∗, xz ∈ L iff yz ∈ L
implies that
∀z ∈ Σ∗, yz ∈ L iff xz ∈ L.
But “iff” is reversible so clearly this holds.
transitivity: Here we must show that ∀x, y, z ∈ Σ∗ if we have (first assumption)
∀w ∈ Σ∗, xw ∈ L iff yw ∈ L
and (second assumption)
∀w ∈ Σ∗, yw ∈ L iff zw ∈ L
then (conclusion)
∀w ∈ Σ∗, xw ∈ L iff zw ∈ L.
Suppose w is some word in Σ∗ and suppose that xw ∈ L, then the first assumption tells us
that yw ∈ L. Using this fact with the second assumption tells us that zw ∈ L. Thus xw ∈ L
implies that zw is in L. Proceeding in the same way, if zw ∈ L we must have yw ∈ L and
thence xw ∈ L. Thus we have established the conclusion.
This is a very pedantically written proof, far too detailed for most tastes. I just want you to have
the sense of what goes into such a proof. In future you can state obvious things as “obvious” but
don’t try and pass off things that are not at all obvious as obvious.
1
Question 2[20 points] Consider, pairs of natural numbers 〈m,n〉 where m,n ∈ N. We order them
by the relation 〈m,n〉 v 〈m′, n′〉 if m < m′ or (m = m′) ∧ n ≤ n′, where ≤ is the usual numerical
order. Prove that the relation v is a partial order. [10 points]
Solution From the definition of a partial order we have to verify that v is (i) reflexive, (ii)
antisymmetric and (iii) transitive. We tackle each property in turn. (i) If we compare 〈m,n〉
with itself we see that m = m so we are in the second case, and here we have n ≤ n so we have
〈m,n〉 v 〈m,n〉 [You may be tempted to just say this is obvious; yes it is and I would accept that,
in this case.] (ii) Suppose that 〈m1, n1〉 v 〈m2, n2〉 and 〈m2, n2〉 v 〈m1, n1〉. Now suppose that
m1 < m2 then it is impossible for 〈m2, n2〉 v 〈m1, n1〉 to hold. So if both hold we must have
m1 = m2. Then we know that n1 ≤ n2 and n2 ≤ n1. But the ordinary ≤ relation is known to
be antisymmetric so n1 = n2. Thus the two pairs are equal as pairs. (iii) Since there are two
possible cases for each instance of the v relation we have 4 combinations to consider. Suppose
〈m1, n1〉 v 〈m2, n2〉 and 〈m2, n2〉 v 〈m3, n3〉. We must show that 〈m1, n1〉 v 〈m3, n3〉.
1. Suppose that m1 = m2, n1 ≤ n2, m2 = m3 and n2 ≤ n3. Then clearly we have m1 = m3
(equality is transitive) and n1 ≤ n3 (the ≤ relation is transitive) so we have 〈m1, n1〉 v
〈m3, n3〉.
2. Suppose m1 < m2 and m2 = m3 then m1 < m3 and we have 〈m1, n1〉 v 〈m3, n3〉.
3. Suppose that m1 = m2 and m2 = m3, again we have m1 < m3 so 〈m1, n1〉 v 〈m3, n3〉.
4. Suppose m1 < m2 and m2 < m3 then m1 < m3 and we have 〈m1, n1〉 v 〈m3, n3〉.
We have checked all possible cases so we conclude that v is transitive and have thus completed the
proof that it is a partial order.
Question 3[20 points] Give deterministic finite automata accepting the following languages over
the alphabet {0, 1}.
1. The set of all words ending in 00.
2. The set of all words ending in 00 or 11.
3. The set of all words such that the second last element is a 1. By “second last” I mean
the second element counting backwards from the end. Thus, 0001101 is not accepted and
10101010 is accepted.
Solutions: The automata are shown in the following pictures:
q0start q1 q2
0
1
0
1
0
1
2
q0start
q1 q2
q3 q4
0
1
0
1
0
1
0
1
0
1
q00start q10
q01 q11
1
0
0
1
0
1
1
0
Question 4[20 points] Suppose that L is a language accepted by a DFA (i.e. a regular language)
show that the following language is also regular:
lefthalf(L) := {w1|∃w2 ∈ Σ∗ such that w1w2 ∈ L and |w1| = |w2|}.
[Hint: nondeterminism.]
Solution Suppose L is defined by (Q,Σ, δ, q0, F ). We will make a new NFA (Q
′,Σ, δ′, Q0, F
′).
Q′ = Q×Q
Q0 = {(q0, f)|f ∈ F}
F ′ = {(s, s)|s ∈ Q}
δ′((s, t), a) = {(δ(s, a), t′)|t = δ(t′, b) for some b ∈ Σ}
The states in the new machine are pairs of states from the old machine. Given a string w, the first
coordinate just keeps track of how the old machine would act on w. The second coordinate acts
3
a bit like the machine for rev(L). It starts in an accepting state from the old machine, and works
backward, keeping track of all the possible paths rev(L) could take, given any input of the same
length as the part of w that the machine has processed at that step. If the machine reaches the end
of w and one path has ended up in a state (s, s), then the machine for L would be in state s upon
reading w. Furthermore since the second coordinate started out in an accepting state and went
backward to s in |w| steps, there is some forward path in the old machine of length |w| starting in
s and ending up in an accepting state. This path defines a string w′ such that |w| = |w′|, and if we
input ww′ into the old machine, it reads w and reaches s, then starting from s and reading w′, it
ends up in an accepting state. So ww′ is in L, and w is accepted by the new machine if and only
if it is in lefthalf(L). Therefore lefthalf(L) is a regular language for any regular language L.
Here is another solution: Suppose L is defined by (Q,Σ, δ, q0, F ). We will make a new NFA
(Q′,Σ, δ′, Q0, F
′).
Q′ = Q×Q×Q
Q0 = {(q0, s1, s1)|s1 ∈ Q}
F ′ = {(s1, s1, s2)|s1 ∈ Q and s2 ∈ F}
δ′((s1, s2, s3), a) = {(δ(s1, a), s2, s4)|s4 = δ(s3, b) for some b ∈ Σ}
Each state of this machine is a triple of states from the old machine. Given a word w, the first
coordinate keeps track of how the old machine would act on w, the third coordinate simultaneously
keeps track of how the old machine would act on any possible input of the same length as what it
has read so far of w starting at any state, and the second coordinate keeps track of whether the
start state of the third coordinate is the same as the end state of the first coordinate. So, if a word
w1 is in lefthalf(L), there is a word w2 with |w1| = |w2| and w1w2 ∈ L. Our machine starts out
in all possible states (q0, q, q). Then at step n + 1, it goes to a state where the first coordinate is
the state that our old machine would be in if it had read the first n characters of w1. The second
coordinate never changes, and the third coordinate is any state the old machine could be in after
reading n characters of any word w2, starting in q, the state represented by the second coordinate.
So, when the machine has read all of w1, if the first coordinate is q, then the old machine would
have arrived in state q after having read w1. And if the last coordinate is also an accepting state,
then there is some word w2 with |w1| = |w2| so that the old machine would reach an accepting state
if it started in q and read w2. Thus, the old machine would read w1, get to q, then read w2 and
finally arrive in an accepting state. Therefore, the new machine accepts exactly lefthalf(L).
Question 5[20 points]
1. Give a deterministic finite automaton accepting the following language over the alphabet
{0, 1}: The set of all words containing 100 or 110. [5 points]
2. Show that any DFA for recognizing this language must have at least 5 states. [15 points]
Solution We need to remember the last two characters seen so far and we need to know that we
have never seen a 1, so intuitively one expects to have 5 states. Of course, this is not a proof that
you really need 5 states. Here is the automaton:
4
q0start q1
q2
q3
q4
1
0
0
1
0
1
1
0
0,1
To prove that 5 states are really necessary we should find 5 strings and show that they all must
end up in different states. If you look at the automaton you can see 5 strings that take you to each
one of the states. These are w0 = ε, w1 = 1, w2 = 10, w3 = 11 and w4 = 100. We have numbered
them so that wi takes you to state qi. Now let us consider any putative recognizer for the language.
Let the states that are reached from the start state by string w0 be called A, the state reached by
w1 be called B and so on to give states A,B,C,D,E. In this machine we do not know that these
are all distinct states; we have to prove that. We will analyze all the possible cases.
• We can see right away that all the states A,B,C,D are different from E since w4 is accepted
and all the others are rejected.
• Suppose A = B so w0 and w1 end up in the same state. Now consider the strings w0 · 00 =
ε · 00 = 00 and w1 · 00 = 1 · 00 = 100. The first string should be rejected and the second one
should be accepted so A and B cannot be the same state.
• Suppose A = C. This is not possible since w0 · 0 = 0 should be rejected and w2 · 0 = 100
should be accepted.
• Suppose A = D. This time we choose to extend the strings by 0 and we get a contradiction.
• Suppose B = C. We choose to extend the strings w1 and w2 by 0 and get a contradiction.
• Suppose B = D. We choose to extend the strings w2 and w3 by 0 and get a contradiction.
• Suppose C = D. We choose to extend the strings w3 and w4 by 10 and get a contradiction.
5