/Users/billy/gits/moc-2021/problem-sets/solps08.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Sample Answers to Problem Set Exercises, Week 8
P8.1 (a) {w | w is not empty and contains only 0s or only 1s}
1
0 0
1
1
0,10
(b) {w | w has length at least 3 and its third symbol is 0}
0,1 0,1 0
1
0,1
0,1
(c) {w | the length of w is at most 5}
0,1 0,1 0,1 0,1 0,1 0,1
0,1
(d) {w | the length of w is a multiple of 3}
0,1
0,1
0,1
(e) {w | every odd position of w is a 1}
0
1
0,1
0,1
(f) {w | w contains at least two 0s and at most one 1}
0 0
0 0
1 1 1
1
1
1
0
0
0,1
(g) {w | the last symbol of w occurs at least twice in w}
1 1
1
0,1
0,1
0
0
0
0
1
0
0,1
1
(h) All strings except the empty string
0,1
0,1
P8.2 (a) {w | w has at least three as} ∩ {w | w has at least two bs}
1 2 3 4 1 2 3
a a a
b b b a,b
b b
a a a,b
1,1 2,1 3,1 4,1
1,2 2,2 3,2 4,2
1,3 2,3 3,3 4,3
a a a
a a a
a a a
b b b b
b b b b
b b b
a
a
a,b
(b) {w | w has an odd number of as} ∩ {w | w ends with b}
1 2 1 2
a
a
b b
b
a
a b
1,1 1,2
2,2 2,1
a
a
b
a
b
a
b
b
(c) {w | w has an even length} ∩ {w | w has an odd number of as}
1 2 1 2
a,b
a,b
a
a
b b
1,1 2,2
2,1 1,2
a
a
bb
a
a
b b
P8.3 (a) {w | w does not contain the substring bb}
b
b
a
a a,b
=⇒
b
b
a
a a,b
(b) {w | w contains neither the substring ab nor ba}
a
b
a
b
a
b a,b
=⇒
a
b
a
b
a
b a,b
(c) {w | w is any string not in A∗ ◦ B∗, where A = {a}, B = {b}}
b a
a b a,b
=⇒
b a
a b a,b
(d) {w | w is any string not in A∗ ∪ B∗, where A = {a}, B = {b}} (compare to (b)!)
a
b
a
b
a
b a,b
=⇒
a
b
a
b
a
b a,b
(e) {w | w is any string that doesn’t contain exactly two as}
a a a
b b b a,b
=⇒
a a a
b b b a,b
(f) {w | w is any string except a and b}
a
b
a,b
a,b
a,b
=⇒
a
b
a,b
a,b
a,b
P8.4 {w | the length of w is a multiple of 2 and is not multiple of 3}
1 2
0,1
0,1
1 2 3
0,1 0,1
0,1
=⇒
1 2 3
0,1 0,1
0,1
1,1 2,2 1,3 2,1 1,2 2,3
0,1 0,1 0,1 0,1 0,1
0,1
P8.5 (i) Suppose L is regular. Then there is some DFA D = (Q,Σ, δ, q0, F ) which recognises L.
Another way to say this is that the language recognised by D is exactly L. We define
the language recognised by D as the set
L(D) = {w ∈ Σ∗ | D accepts w}
We claim that Lc is regular, so we must show that there is a DFAD′ such that L(D′) = Lc.
Let D′ = (Q,Σ, δ, q0, Q \ F ), i.e. it has the exact same set of states, transition function
and start state as D, but all the non-accept states are now reject states (and vice versa).
Then we claim that L(D′) = Lc, since
L(D′) = {w ∈ Σ∗ | D′ accepts w}
= {w ∈ Σ∗ | D rejects w}
= {w ∈ Σ∗ | w 6∈ L(D)}
= {w ∈ Σ∗ | w 6∈ L}
= Lc
Hence Lc is regular, since the DFA D′ recognises it. The core of this proof is the step
“D′ accepts w iff D rejects w”, which can be shown by unwrapping the definition of
acceptance for DFAs. Another way to explain it, is that if D′ rejects w, then after
running D′ on input w, it should finish in a reject state, q 6∈ Q \F , since Q \F is the set
of accept states of D′. But q′ 6∈ Q \ F iff q ∈ F . So if we run D on w, it will take the
exact same transitions and move through the same states as in D′, ending with q, and
q ∈ F , so D must accept w. We can reason similarly to show that if D accepts w then
D′ rejects w.
(ii) Before we dive into the proof, note that we assume L and K are languages over the same
alphabet. If we wanted to intersect languages over distinct alphabets, we could think
of them as languages over the union of their alphabets. Suppose L and K are regular
languages. Then there are DFAs
DL = (QL,Σ, δL, qL0, FL)
DK = (QK ,Σ, δK , qK0, FK)
such that L(DL) = L and L(DK) = K. Define
D
′ = (QL ×QK ,Σ, δ
′
, (qL0, qK0), FL × FK)
where δ′ : (QL ×QK)× Σ → QL ×QK is defined
δ
′((q1, q2), x) = (δL(q1, x), δK(q2, x))
Check that this definition makes sense, by inspecting the function signature of δL :
QL × Σ → QL and δK : QK × Σ → QK , and δ
′.
We claim that L(D′) = L∩K. There are a few ways of reasoning about this. Firstly we
could show by induction on the length of the input string that if DL is in state q1 ∈ QL
after consuming input w, and DK is in state q2 ∈ QK after consuming input w, then
D′ is in state (q1, q2) after consuming input w. This is true by definition for the empty
string, since D′ starts in state (qL0, qK0). Now suppose this true for strings of length n.
We want to show that it’s also true for any string of length n + 1. Let wx be such a
string, where w is a string of length n and x ∈ Σ is a symbol. Then after consuming
input w on each of DL, DK , D
′, if DL is in state q1 and DK is in state q2, we know by
the inductive hypothesis that D′ is in state (q1, q2). After then consuming x on all three
machines, we know that DL will be in state δL(q1, x), and DK will be in state δK(q2, x).
So we just need to show that D′ will be in state (δL(q1, x), δK(q2, x)) after consuming x.
But this is true by definition, since,
δ
′((q1, q2), x) = (δL(q1, x), δL(q2, x))
Then we can show L(D′) = L ∩K directly, since
L(D′) = {w ∈ Σ∗ | D′ accepts w}
= {w ∈ Σ∗ | D′ is in state (q1, q2) after consuming w and (q1, q2) ∈ FL × FK}
=
{
w ∈ Σ∗
∣
∣
∣
DL is in state q1 after consuming w and q1 ∈ FL,
DK is in state q2 after consuming w and q2 ∈ FK
}
=
{
w ∈ Σ∗
∣
∣
∣
DL accepts w,
DK accepts w
}
= {w ∈ Σ∗ | DL accepts w} ∩ {w ∈ Σ
∗ | DK accepts w}
= L ∩K
(iii) Suppose L and K are both regular. Then Kc is regular using (i), and therefore L ∩Kc
is regular using (ii). But L \K = L ∩Kc, so we are done.
P8.6 From this NFA:
1 2 3
4 5
a ǫ
ǫ a
b a
b
b
we get:
1 234 145
35
∅ 5 45
3
b
a
a
a
b
ba
a
b
a
b
a
b
b
a, b
P8.7 From this NFA:
0
1 2 3
4
a
b
a
a
a
a
a
we end up with the following DFA:
0 1
∅ 2 01
034 014
a
b
a
b
b
a
a
b
b
a
b
a
a, b
P8.8 This is the minimal DFA:
1 2
a, b
b
a
P8.9 This is the minimal DFA:
1 2 3
a, b a, b
a
b