/Users/billy/gits/moc-2021/problem-sets/solps09.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Selected Tutorial Solutions, Week 9
P9.1 (i) {w | w has length at least 3 and its third symbol is 0}: (0 ∪ 1)(0 ∪ 1)0(0 ∪ 1)∗
(ii) {w | every odd position of w is a 1}: (1(0 ∪ 1))∗(ǫ ∪ 1)
(iii) {w | w contains at least two 0s and at most one 1}: 0∗(00 ∪ 001 ∪ 010 ∪ 100)0∗
(iv) {ǫ, 0}: ǫ ∪ 0
(v) The empty set: ∅
P9.2 If A is regular then suffix (A) is regular. Namely, let D = (Q,Σ, δ, q0, F ) be a DFA for A.
Assume every state in Q is reachable from q0. Then we can turnD into an NFA N for suffix (A)
by adding a new state q−1 which becomes the NFA’s start state. For each state q ∈ Q, we
add an epsilon transition from q−1 to q.
That is, we define N to be (Q ∪ {q−1},Σ, δ
′, q−1, F ), with transition function
δ′(q, x) =
{δ(q, x)} for q ∈ Q and x ∈ Σ
Q for q = q−1 and x = ǫ
∅ for q 6= q−1 and x = ǫ
The restriction we assumed, that all of D’s states are reachable, is not a severe one. It is
easy to identify unreachable states and eliminate them (which of course does not change the
language of the DFA). To see why we need to eliminate unreachable states before generating N
in the suggested way, consider what happens to this DFA for {ǫ}: ({q0, q1, q2}, {a}, δ, q0, {q0}),
where δ(q0, a) = δ(q1, a) = q1 and δ(q2, a) = q0.
P9.3 (a) Here is an NFA for (ba∗a)∗:
1 2
b
a
a
(b) Here is an equivalent DFA, obtained using the subset construction:
1 2
∅
1,2
b
a
b
a
b
a, b
a
(c) It is easy to get a DFA for the complement:
1 2
∅
1,2
b
a
b
a
b
a, b
a
(d) It would be problematic to do the “complement trick” on the NFA, as it is only guaranteed
to work on DFAs. We would get the following, which accepts, for example, baa:
1 2
b
a
a
(e) Starting from the DFA that we found in (c), we make sure that we have just one accept
state:
1 2
∅
1,2
x
b
a
b
ǫ
ǫ
a
b
a ∪ b
a
Let us first remove the state labeled 1,2:
1 2
∅ x
b
a
b
ǫ
ǫ
aa
∗
b
a ∪ b
Now we can remove state 2:
1
∅ x
a ∪ b(aa∗b)∗b
b(aa∗b)∗
ǫa ∪ b
Finally, eliminating the state labelled ∅, we are left with:
1 x
b(aa∗b)∗ ∪ a(a ∪ b)∗ ∪ b(aa∗b)∗b(a ∪ b)∗
The resulting regular expression can be read from that diagram.
P9.4 (a) We use the pumping lemma to show that B is not regular. Assume that it were. Let p be
the pumping length, and consider ap+1bap. This string is in B and of length 2p+ 2. By
the pumping lemma, there are strings x, y, and z such that ap+1bap = xyz, with y 6= ǫ,
|xy| ≤ p, and xyiz ∈ B for all i ∈ N. By the first two conditions, y must be a non-empty
string consisting of as only. But then, pumping down, we get xz, in which the number
of as on the left no longer is strictly larger than the number of as on the right. Hence
we have a contradiction, and we conclude that B is not regular.
(b) We want to show that C = {w ∈ {a, b}∗ | w is not a palindrome} is not regular. But
since regular languages are closed under complement, it will suffice to show that Cc =
{w ∈ {a, b}∗ | w is a palindrome} is not regular. Assume that Cc is regular, and let p
be the pumping length. Consider apbap ∈ Cc. Since |s| ≥ p, by the pumping lemma,
s can be written s = xyz, so that y 6= ǫ, |xy| ≤ p, and xyiz ∈ Cc for all i ≥ 0. But
since |xy| ≤ p, y must contain as only. Hence xz 6∈ Cc. We have a contradiction, and we
conclude that Cc is not regular. Now if C was regular, Cc would be regular too. Hence
C cannot be regular.
P9.5 Here are the context-free grammars:
(a) {w | w starts and ends with the same symbol}:
S → 0 T 0 | 1 T 1 | 0 | 1
T → 0 T | 1 T | ǫ
(b) {w | the length of w is odd}:
S → 0 | 1 | 0 0 S | 0 1 S | 1 0 S | 1 1 S
P9.6 Here is a context-free grammar for {aibaj | i > j ≥ 0}:
S → A B
A → a | a A
B → b | a B a
P9.7 See Tutorial Sheet 10 solutions
P9.8 Here are some sentences generated from the grammar:
(a) A dog runs
(b) A dog likes a bone
(c) The quick dog chases the lazy cat
(d) A lazy bone chases a cat
(e) The lazy cat hides
(f) The lazy cat hides a bone
The grammar is concerned with the structure of well-formed sentences; it says nothing about
meaning. A sentence such as “a lazy bone chases a cat” is syntactically correct—its structure
makes sense; it could even be semantically correct, for example, “lazy bone” may be a deroga-
tory characterisation of some person. But in general there is no guarantee that a well-formed
sentence carries meaning.
P9.9 We can easily extend the grammar so that a sentence may end with an optional adverbial
modifier:
S → NP VP PP
…
PP → ǫ
PP → quietly
PP → all day
…
P9.10 Here is a suitable NFA: S
B A
a
bb
b
b a
a
a
a b
P9.11 Let w be a string in L(G), that is, w is derived from S. We will use structural induction to show
a stronger statement than what was required; namely we show that, for every string w ∈ L(G),
w starts with neither b nor abb. That is, if w is derived from S then it starts with neither b nor
abb. (To express the property formally, we may write ∀w′ ∈ {a, b}∗(w 6= bw′ ∧ w 6= abbw′).
There is one base case: If w = ab then w does not start b and it does not start with abb.
For the first recursive case, let w = aw′b, where w′ ∈ L(G). By the induction assumption, w′
starts with neither b nor abb. Hence, in this case, w does not start with b (because it starts
with a), and it does not start with abb (because w′ does not start with b).
For the second recursive case, let w = w′w′′, with w′, w′′ ∈ L(G). By the induction assumption,
w′ starts with neither b nor abb (similarly for w′′). Let us do case analysis on the length of
w′.
• |w′| = 0: If w′ = ǫ then w = w′′ which starts with neither b nor abb, by assumption.
• |w′| = 1: In this case we must have w′ = a since, by assumption, w′ does not start with
b. But then w doesn’t start with b, and it doesn’t start with abb either, because w′′ does
not start with b, by assumption.
• |w′| ≥ 2: In this case w′ must start with either aa or ab. That means w does not start
with b. And w can only start with abb if w′ = ab and w′′ starts with b. But the latter
is impossible, by assumption.
Hence in no case does w start with abb.
P9.12 Too easy.
P9.13 Here is a context-free grammar that will do the job (S is the start symbol):
S → ǫ | a A
A → a A | b B
B → ǫ | a A | b B