University of Padua

Department of Information Engineering

Master Degree in Computer Engineering

Automata, Languages and Computation

SELECTED EXERCISES
WITH SOLUTIONS

prof. Giorgio Satta

 Acknowledgments

The exercises and the solutions presented in this collection are based on
the material listed below.

• Collection of exercises with solutions from the class “Informatica Teor-

ica”, within the Bachelor Degree Program in Computer Engineering,
at University of Padua. The exercises were developed during aca-
demic years 1993/94, 1994/95, 1995/96 by students Paolo Chioetto,
Carlo Fantozzi and Ferruccio Fantozzi.

• Collection of exercises with solutions from the class “Informatica Teor-

ica”, within the the First Degree Program in Information Engineering,
at University of Padua. The exercises were developed during academic
years from 2005/06 to 2017/18 by professor Maria Silvia Pini and pro-
fessor Cinzia Pizzi.

• Collection of exercises with solutions from the class “Automi, Lin-

guaggi Formali e Computazione”, within the Second Degree Program
in Computer Engineering, at University of Padua. The exercises were
developed during academic year 2018/19 by students Francesco Caz-
zaro, Samuele Papa and Federico Soldà.

1
 Notation

What follows are some notational conventions related to automata and for-
mal languages, which have not been introduce by the class textbook but
which are quite common in the literature and will be used throughout the
following chapters.

• Symbol N denotes the set of natural numbers, including zero.

• Given two sets S1 and S2 , we write S1 ∖ S2 to denote the set difference

between S1 and S2 .

• Let Σ be a finite alphabet and let L be some language over Σ. We

denote as L the complement language of L, defined as L = Σ∗ ∖ L.

• Let w be a string over an alphabet Σ and let a ∈ Σ. We write #a (w)

to denote the number of occurrences of a in w.

• For a generic string w and an integer i with 1 ≤ i ≤ |w|, we write w[i]

to denote the i-th symbol in w, from left to right.

2
Contents

1 Regular Languages 4

2 Context-Free Languages 18

3 Recursive and Recursively Enumerable Languages 40

3
Chapter 1

Regular Languages

Exercise 1.1 Consider the deterministic finite state automaton A = (Q,

Σ, δ, q0 , F ) with input alphabet Σ = {0, 1}, set of states Q = {q0 , q1 }, initial
state q0 , and final state set F = {q1 }. The transition function δ is graphically
represented in Figure 1.1.
Prove that A recognizes the language

L = {w | w ∈ {0, 1}∗ , #1 (w) odd}.

Solution The textbook explains that to prove the equivalence L = L(A),

where A is a deterministic finite state automaton, we need to define a family
of properties Pq , one for each state q of A. In our case, properties Pq are
defined over the set {0, 1}∗ of binary strings. Next, we must prove that, for
each property Pq and for each string x ∈ {0, 1}∗ , we have that Pq (x) holds
true if and only if δ̂(q0 , x) = q, where q0 indicates the initial state of A.
Informally, this means that Pq (x) is true if and only if, starting from the
initial state and reading x, the automaton reaches state q. The proof must
be developed using the mutual induction technique; see at the end of the
exercise solution for further discussion of this issue.
We proceed by defining the two properties Pq0 and Pq1 .

• For every x ∈ {0, 1}∗ , Pq0 (x) holds if and only if #1 (x) is even.

• For every x ∈ {0, 1}∗ , Pq1 (x) holds if and only if #1 (x) is odd.

We must now prove the following two statements.

(i) For every x ∈ {0, 1}∗ , Pq0 (x) holds if and only if δ̂(q0 , x) = q0 .

4
 0 0

1
Start
q0 q1

Figure 1.1: Graphical representation of the transition function of DFA A

from Exercise 1.1.

(ii) For every x ∈ {0, 1}∗ , Pq1 (x) holds if and only if δ̂(q0 , x) = q1 .
Informally, (i) states that string x has an even number of occurrences of 1 if
and only if, starting from the initial state and reading x, A reaches state q0 .
Similarly, (ii) states that string x has an odd number of occurrences of 1 if
and only if, starting from the initial state and reading x, A reaches state q1 .
Intuitively, for a state q of A the property Pq indicates what language A
would accept if A had q as the only one final state.
At this point we observe that statement (ii) can be used to prove the
statement in the exercise. In fact we have the following chain of equivalences
x ∈ L(A) iff δ̂(q0 , x) = q1 (L(A)’s definition)
iff Pq1 (x) (statement (ii))
iff #1 (x) is odd (Pq1’s definition)
iff x∈L (L’s definition)
which leads us to the conclusion L(A) = L.
To complete the exercise, we must therefore demonstrate the state-
ments (i) and (ii). Since (i) and (ii) are of the form “if and only if”, we
need to prove four statements, and for each statement we need to prove
the base case and the inductive case. As already suggested, we use mutual
induction.
(Part (i), only if) We have to prove that, for every x ∈ {0, 1}∗ , if Pq0 (x)
then δ̂(q0 , x) = q0 . We proceed by induction on the length of x.
Base. We have |x| = 0, which implies x = ε. Since #1 (ε) is even, Pq0 (ε)
holds. Also, by definition of δ̂ we can write δ̂(q0 , ε) = q0 . We conclude then
that the implication holds true.

5
Induction. Let |x| = n > 0. If Pq0 (x) is false, then the implication is always
true. Let’s consider instead the case in which Pq0 (x) is true, that is, #1 (x)
is even. Let us write x = ya with a ∈ {0, 1} and y ∈ {0, 1}∗ , |y| = n − 1.
We need to distinguish two cases, depending on whether a = 0 or a = 1.
• If a = 0, then #1 (y) = #1 (x) and therefore Pq0 (y) holds true. We then
apply the inductive hypotheses for the only if part of statement (i),
and conclude that δ̂(q0 , y) = q0 . From the definition of the transition
function of A, we have that from state q0 and by reading symbol 0 we
can reach state q0 . So we can write
δ̂(q0 , x) = δ(δ̂(q0 , y), 0) = δ(q0 , 0) = q0 .

• If a = 1, then #1 (y) = #1 (x) − 1, that is, #1 (y) is odd, and hence

Pq1 (y) holds. We can then apply the inductive hypothesis for part
only if of statement (ii), and conclude that δ̂(q0 , y) = q1 . From the
definition of the transition function of A, we have that from state q1
and reading symbol 1 we can reach state q0 . Therefore we can write
δ̂(q0 , x) = δ(δ̂(q0 , y), 1) = δ(q1 , 1) = q0 .

This concludes the inductive part of the proof showing the only if part of
the statement (i).
(Part (i), if) We have to prove that, for every x ∈ {0, 1}∗ , if δ̂(q0 , x) = q0
then Pq0 (x) holds. Again, we proceed by induction on the length of string x.
Base. We have |x| = 0, that is, x = ε. The relation δ̂(q0 , ε) = q0 is always
true, by definition of δ̂. Furthermore, Pq0 (ε) is also true, since #1 (ε) is even.
We therefore conclude that the implication is true.
Induction. Let |x| = n > 0. If δ̂(q0 , x) = q0 is false, then the implication we
want to prove is always true. Let’s consider now the case where δ̂(q0 , x) = q0
is true. As before, let us write x = ya with a ∈ {0, 1} and y ∈ {0, 1}∗ ,
|y| = n − 1. We distinguish two cases, depending on whether a = 0 or a = 1.
• Let a = 0. Since δ̂(q0 , x) = q0 , after reading x the automaton must be
in state q0 . The last symbol of x is 0, and from the definition of A we
see that by reading 0 we can reach state q0 only if the automaton is
already in q0 after reading y. Therefore we conclude that δ̂(q0 , y) = q0 .
We can now apply the inductive hypothesis for part if of statement (i),
and conclude that Pq0 (y) is true, that is, y has an even number of
occurrences of 1. Then x also has an even number of occurrences of 1,
and we can assert that Pq0 (x) is also true.

6
 • Let a = 1. Since δ̂(q0 , x) = q0 , the automaton is in state q0 after
reading x. The last symbol of x is 1, and from the definition of A we
see that, by reading 1, state q0 can be reached only if the automaton
is in state q1 after reading y. We then conclude that δ̂(q0 , y) = q1 .
We now apply the inductive hypothesis for part if of statement (ii),
and conclude that Pq1 (y) holds true, that is, y has an odd number of
occurrences of 1. Since #1 (y) = #1 (x) − 1, we conclude that x has
an even number of occurrences of 1, and we can assert that Pq0 (x) is
true.
This concludes the inductive part of the proof, and we have then completed
the if part of statement (i).
The if and the only if parts of statement (ii) can be proved in a very
similar way to the proof of the same parts for statement (i) reported above.
These two proofs are therefore omitted.

Note In this end note to the above exercise, we discuss the need for
the use of mutual induction in the proof of statements (i) and (ii). Let us
consider the inductive case of the only if part of statement (i). We have
discussed two different scenarios, depending on whether string x ends with
0 or 1. In the latter case, we have x = y1, so if x has an even number
of occurrences of 1, then y has an odd number of occurrences of the same
symbol. For this reason, we can’t invoke on y the inductive hypothesis of
the same statement (i) we are proving, which concerns strings with an even
number of occurrences of 1: we must instead invoke on y the inductive
hypothesis of statement (ii), which concerns strings with an odd number of
occurrences of 1. This requires the technique of mutual induction.

Exercise 1.2 Let N = (Q, Σ, δN , q0 , F ) be an NFA with Q = {q0 , q1 , q2 },

Σ = {0, 1}, F = {q2 } and let δN be the transition function represented in
tabular form in Figure 1.2. Construct a DFA D equivalent to N .

Solution In order to construct a DFA D equivalent to N , we exploit the

lazy evaluation construction in which D’s states are produced only when
needed. We start with the initial state q0 of N , which corresponds to the
state {q0 } of D, and we compute all the states that can be reached in the
NFA by reading one occurrence of the two terminal symbols 0 and 1. The
set of states obtained in this way is a single state in the DFA, for which
the transition function will be computed. This DFA state represents the
fact that, in the NFA, we can be in any of the states belonging to the set.

7
 δN 0 1
→ q0 {q0 , q1 } {q1 }
q1 {q1 , q2 } ∅
∗q2 ∅ {q2 }

Figure 1.2: Transition function in tabular form for the NFA of Exercise 1.2.

We recall the reader that the formula to get the next state from a state
{q1 , q2 , . . . , qr } of the DFA, by reading symbol a ∈ Σ, is as follows:
r
[
δD ({q1 , q2 , . . . , qr }, a) = δN (qi , a).
i=1

We report below some among the first states of D, in order of their reacha-
bility from the initial state {q0 }:

δD ({q0 }, 0) = δN (q0 , 0) = {q0 , q1 }

δD ({q0 }, 1) = δN (q0 , 1) = {q1 }
δD ({q0 , q1 }, 0) = δN (q0 , 0) ∪ δN (q1 , 0) = {q0 , q1 } ∪ {q1 , q2 } = {q0 , q1 , q2 }
δD ({q0 , q1 }, 1) = δN (q0 , 1) ∪ δN (q1 , 1) = {q1 } ∪ ∅ = {q1 }
δD ({q1 }, 0) = δN (q1 , 0) = {q1 , q2 }
δD ({q1 }, 1) = δN (q1 , 1) = ∅

In a similar way, we can obtain the remaining states (the intermediate steps
are omitted):

δD ({q0 , q1 , q2 }, 0) = {q0 , q1 , q2 }
δD ({q0 , q1 , q2 }, 1) = {q1 , q2 }
δD ({q1 , q2 }, 0) = {q1 , q2 }
δD ({q1 , q2 }, 1) = {q2 }
δD ({q2 }, 0) = ∅
δD ({q2 }, 1) = {q2 }

The resulting DFA is graphically represented in Figure 1.3.

8
 0

Start 0 0
{q0 } {q0 , q1 } {q0 , q1 , q2 }

1 1 1

0
{q1 } {q1 , q2 } 0

1 1

0
0, 1 ∅ {q2 } 1

Figure 1.3: DFA D equivalent to the NFA with transition table reported in
Figure 1.2.

Exercise 1.3 Construct a DFA recognizing the language of all strings w

over {a, b} such that the third to last symbol in w is b.

Solution The required language can be formally specified as follows

L = {xby | x, y ∈ {a, b}∗ , |y| = 2}.

It’s not difficult to convince oneself that L contains all of the strings whose
third to last symbol is b. Even if the exercise requires to exhibit a determinis-
tic automaton that recognizes L, it is convenient to build a nondeterministic
automaton first. Afterwards, it will be possible to derive a deterministic ver-
sion of the automaton by applying the construction already exploited by the
solution to Exercise 1.2, that is, the construction used in the proof of the
equivalence of languages recognized by the DFA and the NFA classes. The
choice of this procedure stems from the fact that, as often happens, the non-
deterministic automaton has a reduced number of states: this simplifies the

9
specification of the automaton itself, as well as the proof that the recognised
language is the required one.
We therefore specify the NFA M = (Q, {a, b}, δ, q0 , F ), with Q = {q0 , q1 , q2 , q3 }
and F = {q3 }. The transition function δ : Q × {a, b} 7→ 2Q is defined in
Figura 1.4, both in the table and in the graphical form.

stato q0 q1 q2 q3
a {q0 } {q2 } {q3 } ∅
b {q0 , q1 } {q2 } {q3 } ∅

a, b

Start b a, b a, b
q0 q1 q2 q3

Figure 1.4: Transition table and graphical representation of the thransi-

tion function of the nondeterministic automaton M in the solution of Exer-
cise 1.3.

We will now show that the language recognized by M is exactly L, that

is, L(M ) = L. Rather than producing a rigorous proof using the mutual
induction technique, as previously done for Exercise 1.1, we propose here
a shorter but more intuitive argument, although a less rigorous one. The
proof is divided into two parts.
(Part L ⊆ L(M )) Given a generic string z ∈ L, we have to show that
z ∈ L(M ). This result can be obtained by induction on the length of z.
Base. The shortest string in L can be obtained by letting x = ε in the
definition of the language: in this case, we have z = by with |y| = 2, so
that |z| = 3. Starting from the initial state, M can read symbol b, that
is, the first symbol of z, and then move to state q1 , since q1 ∈ δ(q0 , b).
Afterwards, independently from the two symbols composing string y, M
necessarily moves to state q2 and then to the final state q3 , since δ(q1 , a) =
δ(q1 , b) = {q2 } and δ(q2 , a) = δ(q2 , b) = {q3 }. We have then found a path
labeled z = by from the initial state to a final state, and we can conclude
that zL(M ).

10
Induction. Assume |z| > 3; by definition of L, we can write z = xby, with
|x| ≥ 1. Since x contains at least one symbol, we can also write z = Xx′ by,
where X ∈ {a, b} represents the first symbol of x and x′ belongs to {a, b}∗ .
Starting from the initial state, and independently of the specific symbol
X, M can stay in state q0 , since q0 ∈ δ(q0 , a) e q0 ∈ δ(q0 , b). Let us now
observe that the string x′ by also belongs to L, and we have |x′ by| < |z|. By
the inductive hypothesis, then, we derive that x′ by belongs to L(M ), and
therefore there must be some path from q0 to q3 labeled by x′ by. Overall,
we’ve thus shown the existence of a path labeled Xx′ by = z from the initial
state to some final state, and we can conclude that z ∈ L(M ).
(Part L(M ) ⊆ L) For a generic string z ∈ L(M ), we define n = |z| and we
show that z ∈ L(M ) implies z ∈ L. We proceeds by induction on n.
Base. According to the definition of the transition function δ, in order
to move from the initial state to the final state of M we need to visit in
sequence all of the intermediate states of the automaton. Since M has a
total of four states, it takes at least three steps to accept any string. It is
easy to see that the paths of length 3 from q0 to q3 are labeled baa, bab, bba,
bbb. In all cases, b is the third to last symbol, and we can conclude that all
strings accepted by the automaton in three steps belong to L.
Induction. Assume now that n > 3. We observe that, in the first computa-
tion step, M must necessarily stay in state q0 : if it does not, the automaton
would reach in two steps the final state, from which no more moves are
possible. We can then write z = Xx, where X ∈ {a, b} represents the first
symbol of z. String x is accepted by the automaton in less than n steps.
Using the inductive hypothesis, we derive that x belongs to L, and therefore
its third to last symbol is a b. But the third to last symbol of x is also the
third to last symbol of Xx = z. We can then conclude that z ∈ L.
We have concluded our proof that the nondeterministic automaton M
exactly recognizes the language L. To complete the exercise, we now build
an equivalent deterministic automaton M ′ = (Q′ , A′ , B ′ , F ′ ), using the same
technique already exploited in Exercise 1.2. The states in Q′ are subsets of
Q and represent the sets of states in which “different copies” of M can be at
the same time, after reading the same input string. To compute the elements
of Q′ we use the following definition:
r
[
′
δ ({q1 , q2 , . . . , qr }, X) = δ(qi , X), X ∈ {a, b}.
i=1

With this definition, we start with the initial state {q0 } in M ′ , and and

11
compute all reachable states.

δ ′ ({q0 }, a) = δ(q0 , a) = {q0 }

δ ′ ({q0 }, b) = δ(q0 , b) = {q0 , q1 }
δ ′ ({q0 , q1 }, a) = δ(q0 , a) ∪ δ(q1 , a) = {q0 } ∪ {q2 } = {q0 , q2 }
δ ′ ({q0 , q1 }, b) = δ(q0 , b) ∪ δ(q1 , b) = {q0 , q1 } ∪ {q2 } = {q0 , q1 , q2 }
δ ′ ({q0 , q2 }, a) = δ(q0 , a) ∪ δ(q2 , a) = {q0 } ∪ {q3 } = {q0 , q3 }
δ ′ ({q0 , q2 }, b) = δ(q0 , b) ∪ δ(q2 , b) = {q0 , q1 } ∪ {q3 } = {q0 , q1 , q3 }
δ ′ ({q0 , q1 , q2 }, a) = δ(q0 , a) ∪ δ(q1 , a) ∪ δ(q2 , a)
= {q0 } ∪ {q2 } ∪ {q3 } = {q0 , q2 , q3 }
′
δ ({q0 , q1 , q2 }, b) = δ(q0 , b) ∪ δ(q1 , b) ∪ δ(q2 , b)
= {q0 , q1 } ∪ {q2 } ∪ {q3 } = {q0 , q1 , q2 , q3 }
′
δ ({q0 , q3 }, a) = δ(q0 , a) ∪ δ(q3 , a) = {q0 } ∪ ∅ = {q0 }
δ ′ ({q0 , q3 }, b) = δ(q0 , b) ∪ δ(q3 , b) = {q0 , q1 } ∪ ∅ = {q0 , q1 }
δ ′ ({q0 , q1 , q3 }, a) = δ(q0 , a) ∪ δ(q1 , a) ∪ δ(q3 , a)
= {q0 } ∪ {q2 } ∪ ∅ = {q0 , q2 }
δ ′ ({q0 , q1 , q3 }, b) = δ(q0 , b) ∪ δ(q1 , b) ∪ δ(q3 , b)
= {q0 , q1 } ∪ {q2 } ∪ ∅ = {q0 , q1 , q2 }
′
δ ({q0 , q2 , q3 }, a) = δ(q0 , a) ∪ δ(q2 , a) ∪ δ(q3 , a)
= {q0 } ∪ {q3 } ∪ ∅ = {q0 , q3 }
′
δ ({q0 , q2 , q3 }, b) = δ(q0 , b) ∪ δ(q2 , b) ∪ δ(q3 , b)
= {q0 , q1 } ∪ {q3 } ∪ ∅ = {q0 , q1 , q3 }
′
δ ({q0 , q1 , q2 , q3 }, a) = δ(q0 , a) ∪ δ(q1 , a) ∪ δ(q2 , a) ∪ δ(q3 , a)
= {q0 } ∪ {q2 } ∪ {q3 } ∪ ∅ = {q0 , q2 , q3 }
′
δ ({q0 , q1 , q2 , q3 }, b) = δ(q0 , b) ∪ δ(q1 , b) ∪ δ(q2 , b) ∪ δ(q3 , b)
= {q0 , q1 } ∪ {q2 } ∪ {q3 } ∪ ∅ = {q0 , q1 , q2 , q3 }

The set of states of M ′ is

Q′ = {{q0 }, {q0 , q1 }, {q0 , q2 }, {q0 , q1 , q2 },
{q0 , q3 }, {q0 , q1 , q3 }, {q0 , q2 , q3 }, {q0 , q1 , q2 , q3 }}.

The automaton M ′ has eight states, as opposed to the automaton M which

has only four states. From the definition of the subset construction we know
that the number of states of the equivalent DFA can grow exponentially: in
our case, we were expecting a maximum of 16 states. The set F ′ consists of

12
all states in Q′ that contain at least one state in F ; in our case,

F ′ = {{q0 , q3 }, {q0 , q1 , q3 }, {q0 , q2 , q3 }, {q0 , q1 , q2 , q3 }}.

Finally, the transition funcrion δ ′ : Q′ × {a, b} 7→ Q′ can be easily produced

from the previous construction exploring the reachable subsets of Q. We
have therefore completed the definition of the deterministic automaton M ′ .
Since M and M ′ are equivalent, and since we have already shown that
L(M ) = L, we conclude that M ′ recognizes L, as required.

Exercise 1.4 State whether the following languages are regular or not,
and justify your answer:

(i) L1 = {w | w ∈ {a, b}+ , #a (w) ̸= #b (w)};

(ii) L2 = {a, b}∗ · L1 .

Solution L1 is not a regular language. To prove this fact, we introduce

the auxiliary language

L0 = {w | w ∈ {a, b}∗ , #a (w) = #b (w)}

and prove that L0 is not regular using the pumping lemma.

Let us assume that L0 is regular. There exists a constant n such that
each string z ∈ L0 , with |z| ≥ n, can be written as z = uvw, with |uv| ≤ n,
|v| ≥ 1 and uv i w ∈ L0 for every i ≥ 0. Let us consider the string z = an bn ,
which belongs to to the language and has a length strictly greater than n.
We must factorize the string into three parts u, v, w, with |uv| ≤ n and
|v| ≥ 1. Since the first n characters of the string are all a, we must have
u = aj and v = ak , with j + k ≤ n and k ≥ 1. According to the pumping
lemma, also the string z ′ = uv 0 w = uw belongs to L0 : but this statement
is false, since

#a (z ′ ) = #a (u) + #a (w) = #a (z) − #a (v) = n − k;

#b (z ′ ) = #b (u) + #b (w) = #b (w) = #b (z) = n,

with n − k strictly less than n since k ≥ 1. We have therefore established a

contradiction, and we must conclude that L0 is not a regular language.
Let us now observe that L1 = {a, b}∗ ∖ L0 = L0 . Since the class of
regular languages is closed under complementation, if L1 were regular then

13
L0 would also be regular, against what we just have shown. Therefore we
must conclude that L1 is not a regular language.
The language L2 is a regular language. In fact, we will show that L2 =
{a, b}+ , which is a well-known regular language. The proof of this fact is
split into two parts.
(Part L2 ⊆ {a, b}+ ) Let z be a generic string in L2 . According to the
definition of L2 , we can write z = u · v, with u ∈ {a, b}∗ and v ∈ L1 . Since
L1 does not contain the null string, we have v ̸= ε, and therefore z ̸= ε. The
statement of this part now follows immediately, since {a, b}+ contains by
definition each string that is composed of occurrences of a and b, excluding
the null string.
(Part {a, b}+ ⊆ L2 ) Let z be a generic string in {a, b}+ . According to the
definition of L2 , to show z ∈ L2 we have to find strings u and v such that
z = u · v, with u ∈ {a, b}∗ and v ∈ L1 . Since the null string is not included
in {a, b}+ , z contains at least one occurrence of a symbol. Therefore it is
legitimate to place in v the last symbol occurrence in z, and to place in u
all of the remaining symbol occurrences in z. Let us observe that we can
have v = a or v = b, but in either case #a (v) ̸= #b (v), and therefore v ∈ L1
according to the definition of this language. Since u ∈ a, b∗, this concludes
our proof.

Exercise 1.5 Use the closure properties of regular languages to assess

whether the following claims are true or false.

(i) If L = L1 ∪ L2 is regular, then both languages L1 and L2 are regular.

(ii) If L1 is not regular and L2 is regular, then L1 ∩ L2 is always regular.

Solution In order to simplify the presentation, let us assume that both

L1 and L2 are defined over the same alphabet Σ.
(i) If L = L1 ∪ L2 is regular, then both languages L1 and L2 are regular:
this statement is false. To show this fact, we provide a counterexample.
Consider any language L1 which is not regular, and take the union with
L2 = Σ∗ . The result is again Σ∗ , which is a regular language, contrary to
the claim above.
(ii) If L1 is not regular and L2 is regular, then L1 ∩ L2 is always reg-
ular: this statement is false. Again, we provide a simple counterexample.
Consider any non-regular language L1 and perform the intersection with

14
L2 = Σ∗ , which is regular. The result is again L1 , which we have assumed
to be a non-regular language.

Exercise 1.6 State whether the following languages, defined over the al-
phabet Σ = {a, b}, are regular or not, and motivate your answer:

(i) L= = {an bm | n, m ≥ 0, n = m};

(ii) L< = {an bm | n, m ≥ 0, n < m};

(iii) L> = {an bm | n, m ≥ 0, n > m};

(iv) L̸= = an bm | n, m ≥ 0, n ̸= m};

Solution (i) The L= language is not a regular language. To prove this

statement, let us assume by now that L= is indeed regular. Then the pump-
ing lemma should hold. Let n be the constant of the lemma, and let us
choose the string w ∈ L= with w = an bn , which has length |w| ≥ n. We
can write w = xyz, where |xy| ≤ n and |y| = m ≥ 1. The pumping lemma
states, among other things, that the string w′ = xz obtained by eliminating
y from w must be a string of L= . But this is not possible, since w′ = an−m bn
with n − m ̸= n, and we have then violated L= ’s definition. We have there-
fore obtained a contradiction, and we must conclude that L= is not a regular
language.
(ii) The language L< is not regular. We again proceed as above, assuming
that L< is regular. We apply the pumping lemma and choose the string
w ∈ L< with w = an bn+1 , which has length |w| ≥ n. Then we can write
w = xyz, where |xy| ≤ n and |y| = m ≥ 1, and we must have that string
wk = xy k z is still a string of L< , for any value of k with k ≥ 0. This
statement is not verified. In fact, taking for example k = 2, we get the
string w2 = an+m bn+1 . Since m ≥ 1, we have that in w2 the number of
occurrences of symbol a is not smaller than the number of occurrences of
symbol b, as required by L< ’s definition. So we have that w2 ̸∈ L< , against
our initial assumptions. We then have to conclude that L< is not regular.

Note We observe that, even for any other value of k with k ≥ 3 we

have that string wk does not belong to L< , since wk = an−m akm bn+1 and
again the number of occurrences of symbol a in wk is not smaller than the
number of occurrences of symbol b in the same string. However, this last
observation is not necessary to our proof: in fact, to obtain a contradiction

15
to our original assumption about L< being regular, it sufficis to prove that
the pumping lemma is violated for at least one value of k.
(iii) The language L> is not regular. As in previous cases, let us assume
that L> is regular and let n be the pumping lemma constant for the language.
We now choose the string w = an bn−1 , which has length |w| ≥ n. Then we
can write w = xyz, where |xy| ≤ n and |y| = m ≥ 1 and we have that, for
each k value with k ≥ 0, the string wk = xy k z = an−m akm bn−1 must still
be a string of L> . Choosing k = 0, we get the string w0 = an−m bn−1 which
does not belong to L> , since we have m ≥ 1, and therefore in w0 the number
of occurrences of symbol a is not greater than the number of occurrences of
symbol b, as required by L> ’s definition. This allows us to conclude that
L> is not regular.
(iv) Finally, the language L̸= is not regular. However, in this case a
direct application of the pumping lemma would be problematic; the reader
is encouraged to make one attempt in this direction to realize this fact. We
then take a different route with respect to cases (i), (ii) and (iii) above, More
specifically, assuming that L̸= is regular, we will apply operators defined on
regular languages that guarantee that the result is still a regular language,
to arrive at a new language that we will show not to be regular using the
pumping lemma. This allows us to conclude that even L̸= is not a regular
language.
Complementing L̸= with respect to the alphabet Σ = {a, b}, we obtain
the language L̸= formed by all strings that have a certain number of a
followed by the same number of b, as well as all strings that have a and b in
various other positions that do not respect the ai bj pattern. Since we have
assumed that L̸= is regular, L̸= should also be regular. This follows from
the closure property of the regular languages under the complementation
operator.
To make the next part of the proof easier, it is very useful to “filter” the
language L̸= using the auxiliary language

Lab = {ai bj | i, j ≥ 0} .

Such language is regular, since it is generated by the regular expression a∗ b∗ .

Then we have the equality

L̸= ∩ Lab = L= .

This last equality follows from our observation above that the strings in L̸=
are all strings formed by a certain number of a followed by the same number
of b, but also all strings that have occurrences of symbols a and b mixed

16
together, in a way that violates the pattern ai bj imposed by Lab . Since we
are assuming that L̸= is regular, and since we know that Lab is also regular,
language L= must also be regular: this follows from the closure property
of the regular languages under the intersection operator. However, we have
already shown in part (i) of this same exercise that L= is not regular, so we
have obtained a contradiction. We must therefore conclude that L̸= is not
a regular language.

17
Chapter 2

Context-Free Languages

Exercise 2.1 Specify a context-free grammar that generates the language

L = {0n 1m | 0 ≤ n < m}.

Solution The grammar works by initially generating an equal number of 0

and 1 (zero or more) placed at the sides of the start symbol. To conclude the
generation of a string, the grammar goes through an additional variable A
that generates only symbols 1 (one or more). The required context-free
grammar is therefore

G = ({S, A}, {0, 1}, P, S),

where P contains all and only the rules

S → 0S1 | A
A → 1A | 1

In the general case, proving that L(G) = L for a CFG G and a language
L is very complex, the textbook mentions this problem in a special frame
in Chapter 5. The technique used for such proofs is mutual induction, and
the basic idea is the same we have studied for the case of DFAs; see for
instance Exercise 1.1 in Chapter 1. In case of a DFA M , it is necessary
to define properties Pq for each state q of M , and relate each property Pq
with computations of M starting from the initial state and reaching q. In
a similar way, in the case of a CFG G it is necessary to define a property
PA for each variable A of G and relate each property PA to the derivations
of G that start with A and generate a string entirely composed of terminal

18
symbols. In case of the present exercise, G is very simple and uses only two
variables, and therefore the proof of property L(G) = L is relatively simple.
We carry out the proof in the remaining part of this exercise.
Let us start with the definition of the properties associated with the two
variables of G.

• For every x ∈ {0, 1}∗ , PA (x) holds true if and only if x is a sequence
composed by n ≥ 1 occurrences of symbol 1.

• For every x ∈ {0, 1}∗ , PS (x) holds true if and only if x is a sequence
composed by n ≥ 0 occurrences of symbol 0, followed by m > n
occurrences of symbol 1.

We now need to prove the following two statements.

+
(i) For every x ∈ {0, 1}∗ , PA (x) holds true if and only if A ⇒ x.
+
(ii) For every x ∈ {0, 1}∗ , PS (x) holds true if and only if S ⇒ x.

Finally, we observe that PS matches the definition of language L. More

precisely, for each string x ∈ {0, 1}∗ we have that PS (x) holds true if and
only if x ∈ L. Thus statement (ii) above can be used to prove the property
L(G) = L.
To complete the exercise, we must now prove statements (i) and (ii).
Since the statements (i) and (ii) are of the form “if and only if”, we must
prove four statements, and for each statement we must provide the base
case and the inductive case. The technique of mutual induction will be
used in the proof of statement (ii), since the derivations that start with S
and produce strings of terminal symbols use subderivations starting with A.
Conversely, for the proof of statement (i) we only use simple induction, since
the derivations starting with A and producing strings of terminal symbols
do not depend on subderivations starting with S.
+
(Part (i), if) We must prove that if A ⇒ x then PA (x) holds true, for every
x ∈ {0, 1}∗ . We proceed by induction over the length of the derivation.
+ 1
Base. The shortest derivation of the form A ⇒ x is A ⇒ 1 and has length
of one. We have that x is a sequence composed by n ≥ 1 symbols 1, and
therefore PA (1) holds true.
+
Induction. Let us now consider a derivation A ⇒ x with length longer than
one. This derivation must start with the production A → 1A. Then we can
1 + +
write A ⇒ 1A ⇒ 1y, where A ⇒ y. By applying the inductive hypothesis to

19
 +
A ⇒ y we have PA (y), that is, y is a sequence composed by n ≥ 1 occurrences
of symbol 1. It follows that x = 1y is a sequence composed by n ≥ 2
occurrences of symbols 1, and therefore PA (x) holds true.
+
(Part (i), only if) We must prove that if PA (x) holds true then A ⇒ x, for
every x ∈ {0, 1}∗ . We proceed by induction on the length of x.
Base. Let |x| = 1. If x = 1, then PA (1) holds true. The required derivation
1
for x is A ⇒ 1. If x = 0, then PA (0) is false. It follows that the statement
+
“if PA (0) is true then A ⇒ 0” holds true, since the antecedent is false.
Induction. Assuming |x| > 1, we consider the hypothesis that PA (x) holds
+
true and we prove A ⇒ x. We have that x is a sequence composed by n > 1
occurrences of symbols 1. We write x = 1y, with y ̸= ε. Since y contains at
least one occurrence of 1, PA (y) holds true. Since |y| ≤ |x|, we can apply
+
the inductive hypothesis and conclude that A ⇒ y. Using the production
1 +
A → 1A, we can finally write A ⇒ 1A ⇒ 1y = x.
+
(Part (ii), if) We must show that if S ⇒ x then PS (x) holds true, for
x ∈ {0, 1}∗ . We proceed by mutual induction on the length of the derivation.
+ 1 1
Base. The shortest derivation of the form S ⇒ x is S ⇒ A ⇒ 1 and has
length of two. We have x = 1 ∈ L, and therefore PS (1) holds true.
+
Induction. Let S ⇒ x be a derivation of length greater than two. We
+
distinguish two cases, based on the first production in S ⇒ x
+
• If the derivation S ⇒ x starts with the production S → 0S1, then
1 + +
we can write S ⇒ 0S1 ⇒ 0y1 = x. We thus have S ⇒ y. Applying
+
the inductive hypothesis to S ⇒ y we obtain that PS (y) holds true,
that is, y is a sequence composed by n ≥ 0 occurrences of symbol 0,
followed by m > n occurrences of symbol 1. It follows that x = 0y1 is
a sequence composed by n ≥ 1 occurrences of symbol 0, followed by
m > n occurrences of symbol 1, and therefore PS (x) holds true.
+
• If the derivation S ⇒ x starts with the production S → A then we can
1 + +
write S ⇒ A ⇒ x. Since the derivation A ⇒ x has one step less than
+ +
the derivation S ⇒ x, we can apply the mutual induction to A ⇒ x,
deriving that PA (x) holds true, that is, x is a sequence composed by
n ≥ 1 occurrences of symbol 1. This also means that x is a sequence
composed by n ≥ 0 occurrences of symbol 0, followed by m > n
occurrences of symbol 1, and therefore we have that PS (x) holds true.

20
 +
(Part (ii), only if) We must prove that if PS (x) holds true then S ⇒ x, for
x ∈ {0, 1}∗ . We proceed by mutual induction on the length of x.
Base. Let |x| = 1. If x = 1, then PS (x) holds true. The required derivation
1 1
for x is S ⇒ A ⇒ 1. If instead x = 0, we have #0 (0) > #1 (0) = 0. Since the
property PS (x) requires #1 (x) > #0 (x), we conclude that PS (0) is false. It
+
follows that the statement “if PS (0) holds true then S ⇒ 0” is true, since
the antecedent is false.
Induction. Let |x| > 1. We assume the hypothesis that PS (x) holds true,
+
and we prove S ⇒ x. We know that x is a sequence composed by n ≥ 0
occurrences of symbol 0, followed by m > n occurrences of symbol 1. we
distinguish two cases, based on the first symbol in string x
• If x starts with 0, then the last symbol of x must be 1, otherwise we
would have a violation of PS (x). Thus we can write x = 0y1 for some
string y ∈ {0, 1}∗ . Since #0 (y) = #0 (x)−1 and #1 (y) = #1 (x)−1, the
string y is still a sequence composed by n ≥ 0 occurrences of symbol
0, followed by m > n occurrences of symbol 1, and then PS (y) holds
true. Since |y| < |x|, we can apply the inductive hypothesis to y and
+
obtain the relation S ⇒ y. Using the production S → 0S1, we can
1 +
write S ⇒ 0S1 ⇒ 0y1 = x.

• If x starts with 1, we write x = 1y. We know that y ̸= ε. We

also know that there cannot be occurrences of 0 in y, otherwise we
would have a violation of PS (x). Then y is a sequence composed by
n ≥ 1 occurrences of symbols 1, and therefore PA (y) holds true. Since
|y| < |x|, we can apply the mutual induction on y and conclude that
+
A ⇒ y. Using the productions S → A and A → 1A, we can then write
1 1 +
S ⇒ A ⇒ 1A ⇒ 1y = x, which provides the desired derivation for x.

Exercise 2.2 Consider the language

L = {ai bj ck | i, j, k ≥ 1}.

Specify a context-free grammar G that generates L, and use mutual induc-

tion to show the relation L(G) = L.

Solution The basic idea underlying our context-free grammar is to ini-

tially generate a run of a’s through variable S, then switch to variable B to

21
generate a run of b’s, and finally switch to variable C to generate a run of
c’s. The required context-free grammar is therefore
G = ({S, B, C}, {a, b, c}, P, S),
where P consists of the following rules
S → aS | aB
B → bB | bC
C → cC | c
To prove L(G) = L we need to use mutual induction, as in Exercise 2.1.
Let us start with the definition of the properties associated with the three
variables of G. For every w ∈ {a, b, c}∗
• PC (w) holds true if and only if w is a string of k ≥ 1 occurrences of
symbol c;
• PB (w) holds true if and only if w is a string of j ≥ 1 occurrences of
symbol b, followed by k ≥ 1 occurrences of symbol c;
• PS (w) holds true if and only if w is a string of i ≥ 1 occurrences of
symbol a, followed by j ≥ 1 occurrences of symbol b, followed by k ≥ 1
occurrences of symbol c.
We now need to prove the following statements. For every w ∈ {a, b, c}∗
+
(i) PC (w) if and only if C ⇒ w;
+
(ii) PB (w) if and only if B ⇒ w;
+
(iii) PS (w) if and only if S ⇒ w.
Since each of the above statements has the form “if and only if”, we
must prove six statements overall, and for each statement we must provide
the base case and the inductive case. Finally, we observe that PS matches
the definition of language L, thus statement (iii) can be used to prove the
desired property L(G) = L.
+
(Part (i), if) We must prove that if C ⇒ w then PC (w) holds true, for every
w ∈ {a, b, c}∗ . We proceed by induction over the length of the derivation.
+
Base. The shortest derivation of the form C ⇒ w in our grammar G is
1
C ⇒ c and has length one. We have w = c, and it is immediate to see that
PC (w) holds true.

22
 +
Induction. Let us now consider a derivation C ⇒ w with length two or
more. This derivation must start with the production C → cC, and we can
1 +
write C ⇒ cC ⇒ cw′ . We can now use factorization and obtain the shorter
+ +
derivation C ⇒ w′ . By applying the inductive hypothesis to C ⇒ w′ we have
PC (w′ ), that is, w′ is a sequence composed by k ≥ 1 occurrences of symbol
c. It follows that w = cw′ is a sequence composed by k ≥ 2 occurrences of
symbol c, and therefore PC (w) holds true.
+
(Part (i), only if) We must prove that if PC (w) holds true then C ⇒ w,
for every w ∈ {a, b, c}∗ . We proceed by induction on the length of w.
Base. Let |w| = 1. If w = c, then PC (w) holds true. The required
1
derivation for w is then C ⇒ c. If w = a or w = b, then PC (w) is false and
the implication is always true.
Induction. Assuming |w| > 1, we consider the hypothesis that PC (w) holds
+
true and we prove C ⇒ w. Under the above hypothesis, w is a sequence
composed by k > 1 occurrences of symbol c. We can write w = cw′ , with
|w′ | > 0. Since w′ contains at least one occurrence of c, we have that
PC (w′ ) holds true. Since |w′ | ≤ |w|, we can apply the inductive hypothesis
+ 1
and conclude that C ⇒ w′ . Using the derivation C ⇒ cC and composition,
1 +
we can finally write C ⇒ cC ⇒ cw′ = w.
+
(Part (ii), if) We must show that if B ⇒ w then PB (w) holds true, for any
w ∈ {a, b, c}∗ . We proceed by induction on the length of the derivation.
+ 1 1
Base. The shortest derivation of the form B ⇒ w in G is B ⇒ bC ⇒ bc and
has length of two. We can easily see that w = bc and PB (w) holds true.
+
Induction. Let B ⇒ w be a derivation of length greater than two. We
distinguish two cases, based on the choice of the first rule in the derivation.
+
• If the derivation B ⇒ w starts with the rule B → bB, then we can write
1 + +
B ⇒ bB ⇒ bw′ = w. Using factorization we conclude that B ⇒ w′ .
Since the latter derivation is one unit shorter than our initial deriva-
+
tion, we can apply to B ⇒ w′ the inductive hypothesis for statement
“(ii), if”, and derive that PB (w′ ) holds true, that is, w′ is a sequence
composed by j ≥ 1 occurrences of symbol b followed by k ≥ 1 occur-
rences of symbol c. Therefore we have that w = bw′ has the same
structure and PB (w) holds true as well.
+
• If the derivation B ⇒ w starts with the rule B → bC, then we can write

23
 1 +
B ⇒ bC ⇒ bw′ = w. Again, we can use factorization and conclude that
+
C ⇒ w′ . Since the latter derivation is one unit shorter than our initial
+
derivation, we can apply to C ⇒ w′ mutual induction for statement
“(i), if”, and derive that PC (w′ ) holds true, meaning that w′ is a
sequence composed by k ≥ 1 occurrences of symbol c. This in turn
means that w = bw′ is a sequence composed by j ≥ 1 occurrences of
symbol b followed by k ≥ 1 occurrences of symbol c, and thus PB (w)
holds true.

+
(Part (ii), only if) We must prove that if PB (w) holds true then B ⇒ w,
for any x ∈ {a, b, c}∗ . We proceed by mutual induction on the length of w.
Base. The shortest string w such that PB (w) holds true is w = bc. The
1 1
required derivation in G for w is B ⇒ bC ⇒ bc. It is easy to see that no
other string of length 2 satisfies property PB ().
Induction. Let |w| > 2. We work under the hypothesis that PB (w) holds
+
true, and we prove B ⇒ w. From our hypothesis we have that w is a sequence
composed by j ≥ 1 occurrences of symbol b followed by k ≥ 1 occurrences
of symbol c. We distinguish two cases, based on whether the second symbol
in string w is b or c.

• If w has a prefix bb, then we can write w = bw′ and claim that w′ is
a sequence composed by j ≥ 1 occurrences of symbol b followed by
k ≥ 1 occurrences of symbol c. This means that PB (w′ ) holds true.
Since |w′ | < |w|, we apply on w′ induction for statement “(ii), only
+
if”, and we conclude that B ⇒ w′ . Then we can compose the desired
1 +
derivation B ⇒ bB ⇒ bw′ = w.

• If w has a prefix bc, then we can write w = bw′ and claim that w′ is a
sequence composed by k ≥ 1 occurrences of symbol c. This means that
PC (w′ ) holds true. Since |w′ | < |w|, we apply on w′ mutual induction
+
for statement “(i), only if”, and we conclude that C ⇒ w′ . Then we
1 +
can compose the desired derivation B ⇒ bC ⇒ bw′ = w.

+
(Part (iii), if) We must show that if S ⇒ w then PS (w) holds true, for any
w ∈ {a, b, c}∗ . We use mutual induction on the length of the derivation.
+ 1 1 1
Base. The shortest derivation of the form S ⇒ w is S ⇒ aB ⇒ abC ⇒ abc,
with length three. We can easily see that PS (w) holds true for w = abc.

24
 +
Induction. Let S ⇒ w be a derivation of length greater than three. We
distinguish two cases, based on the first rule in the derivation.
+
• If the derivation S ⇒ w starts with rule S → aS, then we can write
1 +
S ⇒ aS ⇒ aw′ = w. Factorizing the derivation we obtain a shorter
+
derivation S ⇒ w′ . We can thus apply the inductive hypothesis, and
conclude that PS (w′ ) holds true, that is, w′ is a sequence composed by
i ≥ 1 occurrences of symbol a, followed by j ≥ 1 occurrences of symbol
b, and followed by k ≥ 1 occurrences of symbol c. From w = aw′ , we
can easily see that w has the same property, and then PS (w) holds
true.
+
• If the derivation S ⇒ w starts with the production S → aB, then we
1 +
can write S ⇒ aB ⇒ aw′ = w. Again, we factorize the derivation, and
+
obtain a shorter derivation B ⇒ w′ . We can then apply to deriva-
+
tion B ⇒ w′ the mutual induction hypothesis for statement “(ii), if”,
deriving that PB (w′ ) holds true. This means that w is a sequence com-
posed by j ≥ 1 occurrences of symbol b followed by k ≥ 1 occurrences
of symbol c. Then w = aw′ is a sequence composed by one occurrence
of symbol a, followed by j ≥ 1 occurrences of symbol b, and followed
by k ≥ 1 occurrences of symbol c. This in turn means that PS (w)
holds true.
+
(Part (iii), only if) We now prove that if PS (w) holds true then S ⇒ w,
for w ∈ {a, b, c}∗ . We proceed by mutual induction on the length of w.
Base. The shortest string in {a, b, c}∗ such that PS (w) holds true is w =
1 1 1
abc. The required derivation for w is S ⇒ aB ⇒ abC ⇒ abc. For all other
strings w ∈ {a, b, c}∗ with length 3 we have that PS (w) is false, and then
the desired implication is true.
Induction. We now consider strings in {a, b, c}∗ with |w| > 3 such that
+
PS (w) holds true, and we prove S ⇒ w. From our hypothesis we have that
w is a sequence composed by i ≥ 1 occurrences of symbol a, followed by
j ≥ 1 occurrences of symbol b, followed by k ≥ 1 occurrences of symbol c.
We distinguish two cases, based on whether the second symbol in string w
is a or b.
• If w has a prefix aa, then we can write w = aw′ and claim that w′
is a sequence composed by i ≥ 1 occurrences of symbol a, followed
by j ≥ 1 occurrences of symbol b, followed by k ≥ 1 occurrences

25
 of symbol c. This means that PS (w′ ) holds true. Since |w′ | < |w|,
+
we apply induction on w′ , and conclude that S ⇒ w′ . Then we can
1 +
compose the desired derivation S ⇒ aS ⇒ aw′ = w.

• If w has a prefix ab, then we can write w = aw′ and claim that w′ is
a sequence composed by j ≥ 1 occurrences of symbol b, followed by
k ≥ 1 occurrences of symbol c. This means that PB (w′ ) holds true.
Since |w′ | < |w|, we apply on w′ mutual induction for statement “(ii),
+
only if”, and we conclude that B ⇒ w′ . Then we can compose the
1 +
desired derivation S ⇒ aB ⇒ aw′ = w.

This concludes the proof that L(G) = L.

For the purpose of gaining a better understanding of the mutual induc-
tion technique, as applied to this typology of problems, we now explore an
alternative solution for this exercise. More precisely, we develop a differ-
ent context-free grammar G′ for generating our language L. The basic idea
underlying G′ is to generate the three runs of a’s, b’s and c’s by means of
three, independent variables A, B, and C, respectively. The new context-
free grammar is specified as

G′ = ({S, A, B, C}, {a, b, c}, P, S),

where P consists of the following rules

S → ABC
A → aA | a
B → bB | b
C → cC | c

Although G′ has some more variables and rules than G, it is somehow simpler
than G since the variables A, B, and C are all mutually independent, and
the rules associated with these variables all work in the same way.
To prove the relation L(G′ ) = L, we define the properties associated
with the variables of G′ . For every w ∈ {a, b, c}∗

• PA (w) holds true if and only if w is a string of i ≥ 1 occurrences of

symbol a;

• PB (w) holds true if and only if w is a string of j ≥ 1 occurrences of

symbol b;

26
 • PC (w) holds true if and only if w is a string of k ≥ 1 occurrences of
symbol c;

• PS (w) holds true if and only if w is a string of i ≥ 1 occurrences of

symbol a, followed by j ≥ 1 occurrences of symbol b, followed by k ≥ 1
occurrences of symbol c.
We now need to prove the following statements. For every w ∈ {a, b, c}∗
+
(i) PA (w) if and only if A ⇒ w;
+
(ii) PB (w) if and only if B ⇒ w;
+
(iii) PC (w) if and only if C ⇒ w;
+
(iv) PS (w) if and only if S ⇒ w.
Again, we observe that PS matches the definition of language L, thus state-
ment (iv) can be used to prove the desired property L(G) = L.
We now observe that the rules for variable C in the two grammars G
and G′ are exactly the same. This means that the proof of statement (i) for
G and the proof of statement (iii) for G′ are the same. We therefore omit
below the proof of statement (iii) for G′ .
Furthermore, we observe that the proofs of statements (i), (ii) and (iii)
for G′ must be very similar, since the rules for the three variables A, B and
C in G′ have the same basic structure. This means that we can omit below
the proofs of statements (i), (ii) as well. We are therefore left with the only
proof of statement (iv).
+
(Part (iv), if) We must show that if S ⇒ w then PS (w) holds true, for any
w ∈ {a, b, c}∗ . We use mutual induction on the length of the derivation.
+
Base. The shortest derivations in G′ having the form S ⇒ w need to use
four steps. There are six such derivations, reported below, and they all
generate the same string w = abc:
1 1 1 1
S ⇒ ABC ⇒ aBC ⇒ abC ⇒ abc ,
1 1 1 1
S ⇒ ABC ⇒ aBC ⇒ aBc ⇒ abc ,
1 1 1 1
S ⇒ ABC ⇒ AbC ⇒ abC ⇒ abc ,
1 1 1 1
S ⇒ ABC ⇒ AbC ⇒ Abc ⇒ abc ,
1 1 1 1
S ⇒ ABC ⇒ ABc ⇒ aBc ⇒ abc ,

27
 1 1 1 1
S ⇒ ABC ⇒ ABc ⇒ Abc ⇒ abc .

It is immediate to see that PS (w) holds true for w = abc.

+
Induction. Let S ⇒ w be a derivation of length greater than four. Since
there is only one rule in G′ for the variable S, the derivation must have the
1 +
form S ⇒ ABC ⇒ w. We now factorize this derivation into three deriva-
tions, one for each of the three variables A, B and C:
+
A ⇒ w1 ,
+
B ⇒ w2 ,
+
C ⇒ w3 ,

for strings w1 , w2 and w3 such that w1 w2 w3 = w. We remark that at this

point we cannot say anything about the terminal symbols appearing in w1 ,
w2 and w3 .
1 +
Assume now that ℓ is the length of the original derivation S ⇒ ABC ⇒ w.
We observe that the sum of the length of the three derivations above must
be ℓ − 1. To see this, consider that each derivation step in the original
derivation appears in exactly one of the three derivations above, with the
1
only exception of the derivation step S ⇒ ABC, which is omitted. Since
all of the three derivations above have length shorter than ℓ, we can apply
mutual induction to each of them.
+
Starting with derivation A ⇒ w1 , we use mutual induction for statement
+
“(i), only if” and obtain that PA (w1 ) holds true. Similarly, from B ⇒ w2 and
+
statement “(ii), only if” we obtain PB (w2 ), and from C ⇒ w3 and statement
“(iii), only if” we obtain PC (w3 ). From these properties and from w =
w1 w2 w3 , we can immediately derive that w is a string of i ≥ 1 occurrences
of symbol a, followed by j ≥ 1 occurrences of symbol b, followed by k ≥ 1
occurrences of symbol c. This in turns means that PS (w) holds true.
+
(Part (iv), only if) We now prove that if PS (w) holds true then S ⇒ w in
G′ , for every w ∈ {a, b, c}∗ . We proceed by mutual induction on the length
of w.
Base. The shortest string such that PS (w) holds true is w = abc. One possi-
1 1 1 1
ble derivation for w, among several ones, is S ⇒ ABC ⇒ aBC ⇒ abC ⇒ abc.
For all other strings w ∈ {a, b, c}∗ with length 3 we have that PS (w) is false,
and then the desired implication is true.

28
Induction. We now consider strings in {a, b, c}∗ with |w| > 3 such that
+
PS (w) holds true, and we show S ⇒ w. From the definition of PS (w), we
have that w is a sequence composed by i ≥ 1 occurrences of symbol a,
followed by j ≥ 1 occurrences of symbol b, followed by k ≥ 1 occurrences of
symbol c. It follows that we can factorize w as w = w1 w2 w3 , such that w1
is a sequence composed by i ≥ 1 occurrences of symbol a, w2 is a sequence
composed by j ≥ 1 occurrences of symbol b, and w3 is a sequence composed
by k ≥ 1 occurrences of symbol c. By definition, we have that PA (w1 ),
PB (w2 ), and PC (w3 ) are all true.
We observe that |w1 | + |w2 | + |w3 | = |w| and |wi | ≥ 1, 1 ≤ i ≤ 3. We
can easily conclude that |wi | < |w|, 1 ≤ i ≤ 3. This means that we can
apply mutual induction to each string wi . Since PA (w1 ), we apply mutual
+
induction for statement “(i), if” and obtain A ⇒ w1 . Similarly, from PB (w2 )
+
and statement “(ii), if” we get B ⇒ w2 , and from PC (w3 ) and statement
+
“(ii), if” we get C ⇒ w3 . Composing these three derivations with derivation
1
S ⇒ ABC, we obtain the derivation
1 + + +
S ⇒ ABC ⇒ w1 BC ⇒ w1 w2 C ⇒ w1 w2 w3 = w
+
which has the desired form S ⇒ w. This concludes the proof that L(G′ ) = L.

Exercise 2.3 Using the pumping lemma for CFL, prove that the language

L = {0i 1j | i, j ≥ 1, j = i2 }

is not a CFL.

Solution Let us suppose that L is a CFL. Then L must satisfy the pump-
ing lemma for context-free languages, and there exits a number n such that,
given a string z ∈ L with |z| ≥ n, we can write z = uvwxy and assert that:

(i) |v| + |x| ≥ 1;

(ii) |vwx| ≤ n;

(iii) uv k wxk y ∈ L for each natural number k ≥ 0.

2
The string z = 0n 1n is in L and satisfies the hypotheses of the pumping
lemma, since |z| = n + n2 ≥ n. However, as we will show below, there is
no choice of vwx in z such that uv k wxk y ∈ L for any choice of k. In the

29
following we viwe the string z as composed by two blocks: a block with n
occurrences of symbol 0, and a block with n2 occurrences of symbol 1. We
now analyze four possible cases, according to the position of vwx relative to
these two blocks.

• vwx is entirely contained in the block composed by 0. For k = 0

the number of occurrences of 0 decreases to a value smaller than n,
since vx ̸= ε, while the number of occurrences of 1 remains unchanged.
Therefore the resulting string uwy does not belong to L.

• vwx is entirely contained in the block consisting of 1. This case is

solved in a similar way to the previous case, by taking k =0.

• If v or x contains occurrences of both 0 and 1, then for k =2 the

resulting string is no longer formed by a block of 0 followed by a block
of 1. Therefore the string uv 2 wx2 y does not belong to L

• The last case takes into consideration the possibility that v consists
only of occurrences of 0, and x consists only of occurrences of 1, and
both of these strings are different from the empty string ε. For a
generic k > 1, let us consider the string zk = uv k wxk y. The number
of 0 in zk is n + (k − 1)|v| and the number of 1 in zk is n2 + (k − 1)|x|.
In order for zk to belong to L we must have

(n + (k − 1)|v|)2 = n2 + (k − 1)|x|,

that is

2n(k − 1)|v| + (k − 1)2 |v|2 = (k − 1)|x|.

We observe now that on the left-hand side of the second equation we

have a term that grows quadratically in k, while on the right we have
a term that grows linearly in k. It follows that the equality cannot be
verified for every value of k.

Having identified at least one value of k for which uv k wxk y ̸∈ L, for

every possible factorization of the string z, we conclude that L is not a
context-free language.

Exercise 2.4 Consider the following language

L = {wwR w | w ∈ {0, 1}∗ }.

30
Produce a PDA that recognizes L or else rigorously prove that L is not a
context-free language.

Solution Following the first suggestion of the exercise, the first thing we
could try is the construction of a PDA that recognizes L. Considering such
construction, however, we soon realize that a nondeterministic PDA could
store w in the stack and then read wR , matching the latter against the stack
content. However, after this process the stack is emptied and the information
about w is no longer available for the third part of the computation. In fact,
the language L is not context-free, as shown below.
Let us suppose that L is a context-free language. Then the pumping
lemma for context-free languages should be satisfied. This in turn means
that there exists a positive integer n such that, given a string z ∈ L with
|z| ≥ n, we can write z = uvwxy such that:

(i) |v| + |x| ≥ 1;

(ii) |vwx| ≤ n;

(iii) uv i wxi y ∈ L for every i ≥ 0.

The string z = 0n 12n 02n 1n is in L, since z = ssR s, with s = 0n 1n , and it

satisfies the hypotheses of pumping lemma, since |z| = 6n > n. However, as
we will show below, there is no choice of vwx within z such that uv i wxi y ∈ L
for any choice of i. First of all, let us view string z as composed of the blocks
shown in Figure 2.1. In what follows, we will also call block of length k any
substring of z composed of k equal characters.

z = 0···01···1 1···10···0 0···01···1

| {z } | {z } | {z } | {z } | {z } | {z }
| I {z II } | III {z IV } | V {z VI }
s sR s

Figure 2.1: Block composition for string z.

There are several places within string z in which vwx can be located.
However, keeping in mind that z consists of 6 blocks of length n, and that
the length of vwx cannot be larger than the length of anyone of these blocks,
we need to consider only 2 possible scenarios, discussed below.

31
 (i) vwx is located within a single block. If we choose i = 0, that is, if
we delete the strings v and x from our factorization of z, then the
resulting string z ′ differs from z by only a single block. We have the
following possible configurations

z ′ = 0j 1n 1n 0n 1n ,
z ′ = 0n 1j 1n 0n 0n 1n = 0n 1j 0n 0n 1n ,
z ′ = 0n 1n 1n 0j 0n 1n = 0n 1n 1n 0j 1n ,
z ′ = 0n 1n 1n 0n 1j ,

where j < n. For none of the above configurations it is possible to view

z ′ as composed by three parts, necessarily of equal length, so that the
definition of L is satisfied.

(ii) vwx is located between 2 blocks. In this case, since |vwx| ≤ n, vwx
can only span over two consecutive blocks. If we choose i = 0, we can
have the following possible configurations for the resulting string z ′′ ,
depending on the position of vwx:

z ′′ = 0j 1k 1n 0n 1n ,
z ′′ = 0n 1j 1k 0n 1n ,
z ′′ = 0n 1j 0k 0n 1n ,
z ′′ = 0n 1n 1j 0k 1n ,
z ′′ = 0n 1n 1n 0j 1k ,

where j and k are natural numbers such that j + k < 2n. Again, for
any of the above choices, we have z ′′ ̸∈ L.

To summarize the above discussion, for each possible factorization of z

there is at least one value of i that violates the pumping lemma. We can
therefore conclude that L is not context-free.

Exercise 2.5 Assess whether the following languages are context-free, and
justify your answer:

(i) L1 = {ap bq ap bq | p, q ≥ 1};

(ii) L2 = {ap bq aq bp | p, q ≥ 1}.

32
Solution The language L1 is not context-free. An intuitive justification
of this fact can be derived by considering how a PDA works. We observe
that a PDA can store one or more non-negative integers by recording in its
stack an appropriate number of symbols, in some order. Later on, the PDA
can access the stored integers by extracting the associated representation
from the stack, in the reverse order. In the case under consideration, p and
q are stored in the stack, but p is inaccessible to the PDA because it is stored
“below q”.
A mathematical proof that L1 is not context-free can be provided using
the pumping lemma for context-free languages. As usual, we start by assum-
ing that L1 is a context-free language, and then we derive a contraddiction.
If L1 is a context-free language, there must be a number n, dependent on
L1 , such that, for an arbitrary string z ∈ L1 with |z| ≥ n, we can write
z = uvwxy and assert that:

(i) |v| + |x| ≥ 1;

(ii) |vwx| ≤ n;

(iii) uv k wxk y ∈ L1 for each natural number k ≥ 0.

We then choose z = an bn an bn ∈ L1 . To be used later, we name each of the

blocks of the string z as shown in Figure 2.2.

| ·{z
z = a · · a} b| ·{z
· · }b a
| ·{z
· · a} b| ·{z
· · }b
I II III IV

Figure 2.2: Factorization of the string z = an bn an bn into named blocks.

The string vwx can be placed at several positions within z. However,

we show below that none of these choices satisfies the pumping lemma. We
distinguish the following possible cases.

• The string vwx consists only of occurrences of symbol a. Since |vwx| ≤

n and since the blocks shown in Figure 2.2 all have length n, we con-
clude that all of the a’s in vwx must necessarily belong to a single
block. We now choose k = 0, i.e., we delete v and x from z. The
resulting string z ′ = uwy has blocks I and III of different lengths,
contrary to the definition of L1 .

33
 • The string vwx consists only of occurrences of symbol b. This case
is similar to the previous one: deleting v and x, the resulting string
z ′ = uwy has blocks II and IV of different lengths, and cannot belong
to L1 .

• The string vwx contains occurrences of both a and b. In this case,

since |vwx| ≤ n, the a block and the b block that are involved must
be consecutive in z. By choosing k = 0, these two blocks get shorter,
while the other two blocks retain their original length. Also in this
case, then, the resulting string cannot be divided into two equal parts,
as require by the definition of L1 .
We therefore conclude that L1 cannot be context-free.
The language L2 , on the other hand, is context-free. In order to prove
this fact, we provide a CFG G and prove that L(G) = L2 . The grammar is
specified as G = (V, T, P, S), where V = {S, A} is the set of variables and
T = {a, b} is the set of terminal symbols. The productions contained in P
are as follows:
1. S → aSb
2. S → aAb
3. A → bAa
4. A → ba
To rigorously prove the equivalence L(G) = L2 , we should proceed using
the mutual induction technique, as in Exercise 2.1. We have already ob-
served that carrying out this type of demonstration is quite laborious, also
for grammars with a small number of variables. We therefore omit this part,
in order not to lengthen too much the presentation of the exercise.

Exercise 2.6 State whether the following languages are context-free, and
motivate your answer:
(i) L1 = {ww | w ∈ {a, b}∗ };

(ii) L2 = L1 · {a, b}∗ .

Solution The language L1 is not context-free. In order to get an intuitive

idea of this claim, try to think of a push-down automaton M that attempts
to recognize L1 . This automaton will be nondeterministic, since there is no
special symbol that indicates where to finish the first part of the input string
and start the second one. Such automaton can certainly store in the stack

34
the sequence of a’s and b’s representing w, but this sequence can then be
retrieved from the stack only in the reverse order; in other words, you can
write w on the stack, but you can only read wR from the stack.
We now provide a rigorous proof of the fact that L1 is not a context-
free language. We initially assume that L1 is a context-free language, and
then apply the pumping lemma for this class of languages, showing that we
reach a contradiction. To apply the pumping lemma, we could for instance
choose the string z = a2n b2n a2n b2n , which belongs to L1 since z = ww with
w = a2n b2n . Following this line, however, we can very soon realize that
the factorization of z according to the pumping lemma requires the analysis
of many possible cases, and for some cases the analysis is quite complex.
It is also unclear which other strings of the language L1 to choose, as an
alternative, in order to simplify the overall analysis. The problem with the
complexity of the analysis of L1 according to the pumping lemma is due to
the fact that the structure of the strings in L1 is not strongly restricted, in
the sense that for a string ww ∈ L1 we do not have specific restrictions on
the substring w, that may then be used to simplify the analysis. To prove
that L1 is not a context-free language, we then choose a different strategy,
combining the application of the pumping lemma with some of the closure
properties of context-free languages, in order to avoid the direct application
of the pumping lemma to L1 .
Again, let us assume that L1 is a context-free language. The lan-
guage must therefore satisfy the closure property with the regular languages.
In particular, let L′ be the language generated by the regular expression
a∗ b∗ a∗ b∗ . Then the language L′1 = L1 ∩ L′ must still be a context-free
language. It is not difficult to see that we can define the language L′1 as

L′1 = {ap bq ap bq | p, q ≥ 0} .

Now the strings of L′1 have a much more restricted form than the strings
of L1 , and the application to L′1 of the pumping lemma for context-free
languages is simpler than in the case of L1 . Actually, we have already
encountered language L′1 at item (i) of Exercise 2.5, and we have already
shown using the pumping lemma that such language is not context-free.
To summarize, we have assumed that language L1 is a context-free lan-
guage, we have applied the closure property of context-free languages with
respect to the intersection with regular languages, and finally we have ap-
plied the pumping lemma for the class of context-free languages. All of this
has led us to a contraddiction. We must therefore conclude that L1 cannot
be context-free.

35
 The language L2 = L1 ·{a, b}∗ is instead a regular language, and therefore
also a context-free language: this answers the question in item (ii) of the
exercise. To show that L2 is a regular language, we now provide a rigorous
proof that L2 = {a, b}∗ .
First of all, we definitely have L2 ⊆ {a, b}∗ , since {a, b}∗ contains all
possible strings over alphabet Σ = {a, b} and, among them, all those in L2 .
Let us now show that {a, b}∗ ⊆ L2 : we will then be able to conclude
that L2 = {a, b}∗ . Let w be an arbitrary string in {a, b}∗ . Since ε ∈ L1 , we
can factorize w as w = ε · w,, that is, w is the concatenation of a string in
L1 and a string in {a, b}∗ . Then we have w ∈ L2 .

Exercise 2.7 Consider the language

L = {w | w ∈ {a, b, c}∗ , #a (w) = #b (w) = #c (w) ≥ 1} .

Prove that L is not a context-free language.

Solution We solve this exercise by applying to L the pumping for context-

free languages. The pumping lemma asserts that if L is a context-free lan-
guage then there exists a constant n, depending only on L, such that for
every string z ∈ L with length greater than or equal to n, z can always
be factorized in the form z = uvwxy, such that |vx| ≥ 1, |vwx| ≤ n, and
uv i wxi y ∈ L for every i ≥ 0.
Let us start by assuming that L is a context-free language, and let n be
the constant of the pumping lemma. We choose the string z = an bn cn . This
string certainly belongs to L, since it contains an equal number of a’s, b’s
and c’s, and in addition |z| = 3n ≥ n. We now look for a way to write z as a
concatenation of five strings u, v, w, x, y that satisfy the three requirements
of the pumping lemma.
Our string z is formed by three consecutive blocks of length n, where
each block is entirely composed by occurrences of only one symbol. Let us
consider the string vwx: since its length must be at most n, there are only
two possible scenarios, discussed below.

• The string vwx is placed entirely within one of the three blocks. We
consider here only the case in which vwx is placed within the block of
a’s, as shown in Figure 2.3: the remaining two cases can be treated
in a similar way. If we set i = 0, we have that the resulting string
uwy will have fewer occurrences of a than occurrences of b and c, and
therefore it will not belong to L.

36
 aaaaa
| {z } aaaaaaaa
| {z } aabbbbbbbbbbbbbbbccccccccccccccc
| {z }
u vwx y

aaaaaaaaaaaaaaabb
| {z } bbbbbbbbbb
| {z } bbbccccccccccccccc
| {z }
u vwx y

aaaaaaaaaaaaaaabbbbbbbbbbbbbbbccc
| {z } cccccc
| {z } cccccc
| {z }
u vwx y

Figure 2.3: Placement of string vwx within the first block of an bn cn .

aaaaaaa
| {z } aaaaaaaabbbb
| {z } bbbbbbbbbbbccccccccccccccc
| {z }
u vwx y

aaaaaaaaaaaaaaabbbbbbbbbb
| {z } bbbbbcccccc
| {z } ccccccccc
| {z }
u vwx y

Figure 2.4: Placement of string vwx across the first two blocks of an bn cn .

• The string vwx is placed across two adjacent blocks. We observe that
vwx cannot be placed across all of the three blocks, because otherwise
vwx would have length greater than n. We consider here only the case
in which vwx is placed across the block of a’s and the block of b’s, as
shown in Figure 2.4: the remaining case can be treated in a similar
way. Again, let us set i = 0. As we can see from Figure 2.4, even if
our factorization preserves the balance between the occurrences of a
and b in the resulting string uwy, there will be a mismatch with the
the occurrences of c, and the string will not belong to L.

The fact that we have not been able to find a way to factorize the string
z in the form uvwxy in such a way that the conditions imposed by the
pumping lemma are satisfied leads us to the conclusion that L cannot be a
context-free language.

Exercise 2.8 State the truth or falsehood of the following statements,

providing a rigorous proof.

37
 (i) Given two non-regular languages L1 and L2 , the language L1 ∪ L2
cannot be regular.

(ii) Given a context-free language L1 , each subset of L1 is still a context-

free language.

(iii) Given a context-free language L1 and given a regular language L2 , the

language L1 ∩ L2 could be a regular language.

(iv) Given a context-free language L1 and given a regular language L2 , the

language L1 ∩ L2 could be a non-regular language.

Solution Statement (i) is false. Let us consider as a counterexample the

two following languages, both defined over the alphabet Σ = {a, b}

L1 = {w | w = an bn , n ≥ 0}
L2 = {w | w = an bm , n, m ≥ 0, n ̸= m}

L1 is a well-known non-regular language. L2 is also a non-regular language,

as we have already seen in Exercise 1.6.
It is not difficult to see that we can define the union of L1 and L2 as

L1 ∪ L2 = {w | w = an bm , n, m ≥ 0}

The language L1 ∪ L2 can be generated by the regular expression a∗ b∗ and

is therefore a regular language. Thus L1 and L2 are a counterexample to
statement (i).
Statement (ii) is false. Let us consider as a counterexample the alphabet
Σ = {a, b, c} and the language L1 = Σ∗ , which is a regular language and
therefore also a context-free language. Let us now consider the language

L = {w | an bn cn , n ≥ 0}

for which we have L ⊆ L1 . Language L is not a context-free language, as

can be easily proved using the pumping lemma for context-free languages.
L is therefore a counterexample to statement (ii).
Statement (iii) is true. To show this, we provide a simple example.
Consider the alphabet Σ = {a, b} and the following two languages

L1 = {w | an bm , n, m ≥ 0}
L2 = Σ ∗

38
L1 is a regular language, as already seen in point (ii), and therefore also a
context-free language. L2 is definitely a regular language. We also have the
relationship L1 ∩ L2 = L1 , which proves statement (iii).
Statement (iv) is true. To show this, we again provide a simple example.
Consider the alphabet Σ = {a, b} and the two languages
L1 = {w | an bn , n ≥ 0}
L2 = Σ∗
L1 is a well-known context-free language but not a regular language, and L2
is definitely a regular language. It is easy to see that we have L1 ∩ L2 = L1 ,
which proves statement (iv).

Exercise 2.9 Consider the operator P defined as follows. For each lan-
guage L
P (L) = {x | x ∈ L, |x| = 2n, n ∈ N} .
Is the class of context-free languages closed with respect to operator P ?

Solution To solve this exercise we have to show that, for each context-
free language L, P (L) is still a context-free language. To prove this property
we can take advantage of the fact that the intersection of a context-free
language with a regular language is still a context-free language. In our
case, the language P (L) consists of all the strings from language L having
even length. We can then use as language L′ in the intersection the regular
language formed by all the strings of even length in Σ∗ , where Σ is the
alphabet of the language L.
The fact that L′ is a regular language can easily be verified noting that
′
L = L(M ), where M is the DFA defined as
M = ({q0 , q1 }, Σ, δ, q0 , {q0 })
where the transition function δ is specified as
δ(q0 , a) = q1 , a∈Σ;
δ(q1 , a) = q0 , a∈Σ.
Since L ∩ L′ = P (L), we can concluded that the class of context-free lan-
guages is closed under the operator P .

39
Chapter 3

Recursive and Recursively

Enumerable Languages

Exercise 3.1 Consider the alphabet Σ = {a, b} and the language

L = {w | w ∈ Σ∗ , w = an bban , n ≥ 0}.

Specify a Turing machine that accepts L and stops for every possible input
in Σ∗ .

Solution The required Turing machine is based on a cycle looking for

the two occurrences of symbol a placed at the two ends of the input, to be
replaced with the B (blank) symbol. At the end of this cycle, the machine
accepts if the tape contains only two occurrences of symbol b, one next to
the other.
More precisely, M uses the following strategy.
• In state q0 , M reads a a at the beginning of the input string, erases it
by replacing it with the B, and moves to the right by entering state
q1 .
• In state q1 , M moves to the right leaving the tape unchanged, until it
reaches the first occurrence of B. At this point M goes back to the
left by one tape cell, therefore positioning itself at the rightmost cell
with a symbol different from B, entering state q2 .
• In state q2 , M pretends to read a. If there is no such symbol at the
rightmost position of the working tape, M stops in a non-accepting
state. If M reads instead an a, it deletes it replacing with B, and
moves to the left of a position, entering state q3 .

40
 a/a → a/a ←
b/b → b/b ←

Start a/B → B/B ← a/B ←

q0 q1 q2 q3

B/B →
b/b →

b/b → B/B →
q4 q5 q6

Figure 3.1: Graphical representation of the transition function of the TM

from Exercise 3.1.

• In state q3 , M moves to the left leaving the tape unchanged, until it

reaches the first B. At this point, M moves to the right of the current
cell, therefore positioning itself at the beginning of working tape, and
enters state q0 restarting with the above cycle.

• If M is in state q0 reading b, it moves to the right by one cell, leaving

the tape unchanged and entering state q4 and, if it can read a second
occurrence of b, it still moves to the right by one cell, leaving the tape
unchanged and entering the state q5 . Finally, if in state q5 M reads
B, then it enters the accepting state q6 and stops.

Formally, the required TM is defined as M = (Q, Σ, Γ, δ, q0 , B, {q6 }),

where Q = {q0 , q1 , . . . , q6 }, Γ = Σ ∪ {B}, and the transition function δ is
represented graphically in Figure 3.1.

Exercise 3.2 Let Σ = {0, 1} and consider the language over Σ defined as

L = {w | w ∈ Σ∗ , #0 (w) = #1 (w)}.

Specify a Turing machine that accepts L and halts for every possible input
in Σ∗ .

41
Solution The required TM M uses two different computation phases. In
the first phase, M scans the tape from left to right, looking for the first
occurrence of a 0, and then replaces this occurrence with the special symbol
X. At this point M repositions its head at the beginning of the tape. The
second phase is similar to the first: M scans the tape again from left to right,
looking for the first occurrence of a 1, and replaces it with the special symbol
Y . Then M repositions its head at the beginning of the tape. Altogether, a
computation of M if formed by a cycle in which phases one and two above
alternate. The cycle ends when there are no more occurrences of 0 or 1 in
the tape. In such condition, M halts in a final state, therefore accepting the
input string. In all other cases, M stops without accepting.
More precisely, M uses the following strategy.

• In state q0 , M starts from the beginning of the tape and proceeds to

the right. When reading an occurrence of 0, M replaces it with the
character X, and moves to the left by one tape cell, entering state q1 .

• In state q1 , M moves to the left leaving the tape unchanged. Note that
the encountered symbols can only be 1, X, Y , since the occurrences of
0 have all been replaced. When M reaches the first B (blank), it moves
to the right by one tape cell, and positions itself at the beginning of
the tape, entering state q2 .

• In state q2 , M starts from the beginning of the tape and proceeds to

the right. When reading an occurrence of 1, M replaces it with the
character Y , and moves to the left by one tape cell, entering state q3 .

• In state q3 , M moves to the left leaving the tape unchanged. Note that
the encountered symbols can only be 0, X, Y , since the occurrences of
1 have all been replaced. When M reaches the first B, it moves to
the right by one tape cell, and positions itself at the beginning of the
tape, entering state q0 and restarting the previous cycle.

• If M is in state q0 , moving to the right in search of the leftmost occur-

rence of 0 in the tape, and reads a B character, then M has reached
the end of the tape and must conclude that there are no more occur-
rences of 0 on the tape. In this case M leaves B unchanged, moves to
the left by one tape cell, and enters state q4 .

• In state q4 , M runs the tape to the left to verify that there are no
unprocessed occurrences of 1. If this is the case, M enters the final
state q5 , indicating acceptance of the input string, and halts. In all

42
 1/1 → 1/1 ← 0/0 → 0/0 ←
X/X → X/X ← X/X → X/X ←
Y /Y → Y /Y ← Y /Y → Y /Y ←

Start 0/X ← B/B → 1/Y ←

q0 q1 q2 q3

B/B →
B/B ←

X/X ← B/B →
q4 q5
Y /Y ←

Figure 3.2: Graphical representation of the transition function of the TM

from Exercise 3.2.

remaining cases, i.e. in cases not covered in the description reported

above, M halts without accepting.

Formally, we define the TM M as follows

M = (Q, Σ, Γ, δ, q0 , B, {q5 }),

Q = {q0 , q1 , . . . , q5 },
Γ = Σ ∪ {X, Y, B}.

The transition function δ is graphically represented in Figure 3.2.

Exercise 3.3 Consider the alphabet Σ = {a, b} and the symbol c ̸∈ Σ.

Specify a TM with output that, given any string w ∈ Σ∗ , produces as
output the string wcw and halts.

Solution The required TM M must write on its tape the string wcw.
Initially M writes a c at the end of the input string, and then it positions
its tape head at the beginning of the input string. At this point M enters a
cycle in which it performs the following actions. M reads the first character

43
 a/a → a/a ← a/a →
b/b → b/b ← b/b →

Start B/c ← B/B → a/X →

q0 q1 q2 q3

c/c ← b/Y → c/c →

X/a ← q8 a/a → q6 q4 a/a →

Y /b ← b/b → b/b →

B/B → c/c → X/X → B/a ←

Y /Y →
B/b ← a/a ←
q9 a/a → q7 q5 b/b ←
b/b →
c/c ←

Figure 3.3: Graphical representation of the transition function of the TM

from Exercise 3.3.

of w not yet copied, and replaces it with X or Y depending on whether

this character is a or b, respectively. Recording the character in its internal
state, M copies it at the end of a new string to the right of c. When all the
characters of the string w to the left of c have been replaced by X or Y , M
will have entirely copied w to the right of c. At this point, M replaces every
X with a and every Y with b, restoring the initial string w to the left of c.
More precisely, M uses the following strategy.

• In state q0 , M starts from the beginning of the tape and proceeds to

the right. When M reaches the first character B (blank), M rewrites
it with symbol c, and moves to the left by a tape cell, entering state q1 .

• In state q1 , M proceeds to the left. When the first character B is

reached, M leaves it unchanged and moves to the right by a tape cell,

44
 entering state q2 . At this point M is placed at the beginning of the
input string w.

• In state q2 , M starts a cycle. If the read symbol is a, M replaces it

with X, moves all the way to the right, and copies a in place of the
first B it encounters. To do this, M passes through states q3 , q4 and
q5 . Symmetrically, if the read symbol is b, M replaces it with Y and
copies the b in place of the first B it encounters when moving to the
right, passing through states q6 , q7 and q5 .

• In state q5 , M proceeds to the left until it reaches an occurrence of

either X or Y . At this point M moves to the right by one tape cell,
entering state q2 . In this last state, if M reads a or b, it means that
there are symbols of the input string that have not yet been copied,
so M restarts its main cycle. If M reads the c character instead, then
all symbols of the input string have been copied. In the latter case M
moves to the left of a cell, and enters state q8 .

• In state q8 , M proceeds to the left, replacing each X with a and each

Y with b. When M reaches the first symbol B, M leaves it unchanged
and moves to the right by a tape cell, enters the final state q8 and
accepts.

Formally, we define the TM M as follows

M = (Q, Σ, Γ, δ, q0 , B, {q9 }),

Q = {q0 , q1 , . . . , q9 },
Γ = Σ ∪ {c, X, Y, B}.

The transition function δ of M is graphically represented in Figure 3.3.

Exercise 3.4 Let L1 be a recursive language which is not CFL. Consider

the following property of the recursively enumerable (RE) languages:

P = {L | L ∈ RE, L ⊆ L1 }.

Let LP = {enc(M ) | L(M ) ∈ P}, where enc(M ) represents an encoding of

the Turing machine M . Assess whether LP is a recursive language.

Solution By applying Rice’s theorem we can very often solve exercises as

this one, asking to assess whether LP is a recursive language. Rice’s theorem

45
states that if the property P is non-trivial, that is if P ̸= RE and P ̸= ∅,
then P is not decidable. Recall that a property P of the RE languages is
decidable if the language LP is recursive, where LP consists of strings that
are codings of Turing machine that accept languages in P.
We certainly have P = ̸ ∅: in fact L1 is recursive, and therefore it is also
in RE, and it belongs to P since L1 ⊆ L1 . We also have P = ̸ RE, although
this verification is slightly more complex. We observe that L1 ̸= Σ∗ , because
otherwise L1 would be regular, and therefore also context-free, violating the
hypothesis. Then there exists at least one string w ∈ Σ∗ that does not
belong to L1 . We can then choose L2 = {w} as a RE language that is not
a subset of L1 and therefore does not belong to P.
Applying now Rice’s theorem, we conclude that P is not decidable, so
LP is not recursive.

Exercise 3.5 Let w be a string in Σ∗ . Consider the following property of

the recursively enumerable (RE) languages:

P = {L | L ∈ RE, w ∈ L}.

Let also LP = {enc(M ) | L(M ) ∈ P}. Assess whether

(i) LP is recursive;

(ii) LP is recursively enumerable.

Solution As a first question, the exercise asks whether LP is recursive.

For this point we can apply Rice’s theorem, and check whether P is a trivial
property.
First, we have that P ̸= ∅. To see this, we observe that L1 = {w}
is certainly a recursively enumerable language. This follows from the fact
that L1 is a finite language and thus a regular language, and the class of
regular languages is included in the class RE. Furthermore, L1 contains w
and therefore L1 ∈ P. Second, we have P = ̸ RE. To see this, we observe
that the language L2 = {z} with z a string different from w, is certainly
a recursively enumerable language (from the same argument as above) but
does not belong to P since it does not contain the string w.
We have thus shown that the property P is not trivial. At this point we
can apply Rice’s theorem and conclude that LP is not recursive.
We now move on with the second question of the exercise. It is quite
easy to specify a TM MP accepting LP .

46
 • MP receives as input a string z and checks if it is a valid encoding
enc(M ) of some TM M . If not, then MP halts in a non-final state.

• MP simulates M on input w. If M accepts, then MP also accepts.

Note that, at the second item above, M could not halt on input w. In this
case also MP would not halt. Since LP is not recursive, this scenario can
not be avoided.
The following chain of logical equivalence relations formally proves that
L(MP ) = LP :

enc(M ) ∈ L(MP ) iff w ∈ L(M ) (definition of MP )

iff L(M ) ∈ P (definition of P)
iff enc(M ) ∈ LP (definition of LP ).

Exercise 3.6 Let Σ be some alphabet and let a ∈ Σ. Consider the follow-
ing property of recursively enumerable (RE) languages:

P = {L | L ∈ RE, #a (w) ≥ 4 for each w ∈ L}.

Let LP = {enc(M ) | L(M ) ∈ P}. State whether LP is a recursive lan-

guage.

Solution To assess whether LP is recursive, we check the hypotheses of

Rice’s theorem.
First, we show that P = ̸ ∅. To see this, consider the language L1 =
{aaaaa}. L1 is a finite language, and therefore also a recursively enumerable
language. Furthermore, its only string contains more than four occurrences
of a and therefore L1 belongs to P.
Second, P ≠ RE. To see this, we need to construct a recursively enu-
merable language in which for at least one string w we have #a (w) ≤ 4. A
simple choice is for instance L2 = {aa}.
Let us note that, in the construction of L1 and L2 , we have only used
the symbol a: this is the only symbol that belongs to Σ for sure; as far as
we know, the alphabet might be composed by only one symbol!
Having verified that P is non-trivial, we now apply Rice’s theorem and
conclude that LP is not recursive.

47
Exercise 3.7 Let L be a generic language defined over an alphabet Σ. Let
us define the prefix operator

pref(L) = {w | wx ∈ L, w ∈ Σ∗ , x ∈ Σ+ }.

In words, pref(L) contains all proper prefixes of strings from L, that is, all
strings that when prolonged by means of one or more occurrences of certain
symbols from Σ can form a string in L.
Show that the class RE of all recursively enumerable languages is closed
under the prefix operator.

Solution To solve the exercise we show that, for any language L in RE,
we can construct a nondeterministic Turing machine N such that L(N ) =
pref(L). We know that we can always convert N into a deterministic Turing
machine, and therefore we can conclude that pref(L) is a language in RE.
Let M be a deterministic Turing machine such that L(M ) = L; M exists
since we have assumed that L is an RE language. To accept all and only the
strings in pref(L), the nondeterministic Turing machine N uses the following
strategy.

• Using nondeterminism, N “guesses” a string x ∈ Σ+ .

• Next, N concatenates the input string w with x, and simulates M on

wx. If M accepts, then N accepts as well; if instead M stops without
accepting or else if it does not stop, then N does the same.

It is not difficult to see that L(N ) = pref(L). In fact, if a string wx is

accepted by N , then wx is also accepted by M and therefore wx ∈ L. Since
we have chosen x other than the empty string ε, we can conclude that w is a
proper prefix of some string in L, and therefore w ∈ pref(L). In the opposite
direction, if w ∈ pref(L) by definition there exists some non empty string x
such that wx ∈ L. Then, among the many nondeterministic calculations of
N , there must be a computation that generates x and simulates M on wx.
Since M accepts wx, N accepts w.
Alternative solution We can solve the exercise by directly building a
deterministic Turing machine Md such that L(Md ) = pref(L). This alterna-
tive proof gives us the opportunity of introducing a technique which is fairly
widespread in standard exercises about computability theory.
As in our previous solution, le M be a deterministic Turing machine such
that L(M ) = L. We might then think about building Md in such a way that
it generates all strings x ∈ Σ+ , one at a time, and then dispatches string

48
wx to M as an input. However, this idea hides a severe mistake. Consider
xi , the i-th string in Σ+ assuming the lexicographic order. Computation of
M on wxi might never stop, according to the definition of languages in RE.
In this case, any strings wxj ∈ L with j > i would never be examined, and
therefore the machine Md would not have the correct behavior.
The problem can be solved by inserting into Md a pair generator G. The
latter produces as output all possible pairs of natural numbers (i, j) with
i, j > 0. G can easily be realized by increasing some counter k, starting from
2, and printing for each value of k all pairs of positive integers satisfying
i + j = k, sorted by growing values of i. The integer pairs are therefore
generated by G in the following order

(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), . . .

Every time G generates a pair (i, j), Md performs a simulation of the TM

M on wxi for exactly j computation steps, after which we move on with the
next pair generated by G. In this way, we can avoid infinite computations.
So let us assume that there exists some string in L having the form wxi .
Then M accepts wxi in some number j of computation steps. Furthermore,
pair (i, j) must be generated by G after some finite number of steps. At
that point, Md successfully completes the simulation of M on wxi , and
therefore accepts w. On the other hand, if there is no string xi ∈ Σ+ such
that wxi ∈ L, then none of the simulations of M for a finite number of
computation steps will ever be successful, and Md will continue to cycle
endlessly without ever accepting the input string w.

Exercise 3.8 Let L1 be a finite language. Consider the following property

of the recursively enumerable (RE) languages:

P = {L | L ∈ RE, L1 ∩ L ̸= ∅}.

Let LP = {enc(M ) | L(M ) ∈ P}. Assess whether

(i) LP is recursive;
(ii) LP is recursively enumerable.

Solution We need to distinguish between two different cases, depending

on whether L1 is the empty language or not.
L1 = ∅. Then the property P is trivial. To see this, observe that
any language intersected with L1 provides the empty language. Then no

49
recursively enumerable language can satisfy the condition L1 ∩ L ̸= ∅ in
the definition of property P, and therefore P = ∅. In this case LP = ∅,
and it is certainly a recursive language, since it is recognized by a TM that,
regardless of the given input, always halts without accepting. Of course, LP
is also a recursively enumerable language.
L1 ̸= ∅. We start again from the verification of the hypotheses of Rice’s
theorem. First, we observe that P = ̸ ∅. To see this observe that L1 is a finite
language, and therefore also a regular language. Since the class of regular
languages is included in the class of recursively enumerable languages, we
have that L1 is a recursively enumerable language. Furthermore, we have
L1 ∈ P, since L1 ∩ L ̸= ∅ for L = L1 .
Second, P does not include all recursively enumerable languages. To see
this, we use the fact that L1 is a finite language. Therefore there exists a
string w ∈ Σ∗ such that w ̸∈ L1 . Then we can define L2 = {w}, which
is a recursively enumerable language. Furthermore, we have L2 ̸∈ P, since
L1 ∩ L = ∅ for L = L2 . Applying now Rice’s theorem, we have that LP is
not recursive.
Under the assumption that L1 ̸= ∅, the language LP is a recursively
enumerable language. To see this, assume that the strings in the finite
language L1 are sorted according to the lexicographical ordering. For each
j with 1 ≤ j ≤ |L1 |, let wj be the j-th string of L1 . Consider then the TM
MP specified by means of the following steps.

• MP receives as input a string z and checks whether z is a valid encoding

enc(M ) of a TM M . If not, MP halts in a non-final state.

• MP sets i = 1.

• For each j, 1 ≤ j ≤ |L1 |, MP simulates M on wj for exactly i steps. If

M accepts at least one string wj in i steps, then MP halts and accepts.

• MP increments by one unit the value of i.

• MP iterates starting at third item above.

The simulation of M for a limited number of steps i is needed to avoid

computations on some strings that may take forever. In fact, assume that
M does not halt after any finite number of steps on some string wj ∈ L1 .
In this case, if MP would not impose any time limit on its simulation of M
on wj , then MP would never be able to examine the next string wj+1 . But
wj+1 could perhaps be the string witnessing that the intersection between
L1 and L(M ) is not empty.

50
 As already done for some previous exercises, we now show that L(MP ) =
LP through a chain of equivalences:

enc(M ) ∈ L(MP ) iff M accepts some string w ∈ L1

iff L1 ∩ L(M ) ̸= ∅
iff L(M ) ∈ P
iff enc(M ) ∈ LP .

Exercise 3.9 Consider the following language

L = {enc(M, M ′ ) | L(M ) ∩ L(M ′ ) ̸= ∅}

where M, M ′ are generic TMs and enc(M, M ′ ) is a string representing a

fixed encoding for M, M ′ . Prove that L is not a recursive language. (Hint:
reduce from Lu to L.)

Solution We must show that there is no algorithm that can recognize

all and only the strings in L, i.e., that there is no TM that recognizes L
and halts for every possible input string. At first sight, one might think
that to solve this exercise, Rice’s theorem should be exploited. However, a
closer look reveals that this is not the right way to proceed. In fact, Rice’s
theorem only applies to languages of the form {enc(M ) | L(M ) satisfies
some property P of RE languages}. This is not the case for the exercise at
hand, where each instance has instead the form enc(M, M ′ ), that is, each
instance represents the encoding of a pair of TMs, not just one.
To solve the exercise, we instead follow the hint provided in the text and
prove that the universal language Lu defined in the textbook can be reduced
to L, which we denote by writing Lu ≤m L. This means that deciding
whether a string belongs to L is at least as difficult as deciding whether a
string belongs to Lu . Since the universal language Lu is undecidable, as
shown in the textbook, we conclude that also L must be undecidable.
To prove Lu ≤m L, we must provide a construction (basically, a TM) that
transforms any string of the type enc(M, w), which represents an instance of
the problem associated with Lu , into a string enc(M1 , M2 ), which represents
an instance of the problem associated with our target language L. In order
for our construction to represent a valid reduction, the two TMs M1 and
M2 must satisfy the condition

L(M1 ) ∩ L(M2 ) ̸= ∅ if and only if w ∈ L(M ).

51
 yes -
w - M
x - M
1

Figure 3.4: The TM M1 in the solution of Exercise 3.9.

A possible pair M1 , M2 satisfying the above condition is obtained by taking

two identical copies of the TM reported in Figure 3.4. More precisely, M1
and M2 are identical and are constructed in such a way that
 ∗
Σ , if w ∈ L;
L(M1 ) = L(M2 ) =
∅, if w ̸∈ L.

To see that M1 and M2 satisfy the required condition, we observe that if

w ∈ L(M ), we have L(M1 ) ∩ L(M2 ) = Σ∗ and therefore L(M1 ) ∩ L(M2 ) ̸= ∅.
If instead w ̸∈ L(M ), the language accepted by each of the two machines is
∅ and therefore L(M1 ) ∩ L(M2 ) = ∅.
We have therefore shown that Lu ≤m L. Since Lu is not a recursive
language, our reduction completes the exercise.
An alternative way to prove the reduction Lu ≤m L is as follows. As
above, let enc(M, w) be the input instance and let enc(M1 , M2 ) be the output
instance of the construction. We then let M1 = M and M2 = Mw , where
Mw is a special TM that recognizes the language {w}, that is, Mw accepts
only the string w. We can easily see that

{w}, if w ∈ L(M )
L(M ) ∩ L(Mw ) =
∅, if w ̸∈ L(M )

which is exactly the desired condition.

Alternative solution. An alternative solution for this exercise is to
reduce from Lne to L, where

Lne = {enc(M ) | L(M ) ̸= ∅}

is a language introduced in the textbook, where it is also shown that Lne is

not recursive.

52
 Let enc(M ) be an instance of the decision proble associated with Lne ,
that is, enc(M ) is the encoding of a TM for which we have to test whether
L(M ) ̸= ∅. The reduction produces an instance enc(M, M ) of L, that is, a
string representing the encoding of two copies of M . The following chain of
logical equivalences shows that the proposed construction represents a valid
reduction:
enc(M, M ) ∈ L iff L(M ) ∩ L(M ) ̸= ∅ (definition of L)
iff L(M ) ̸= ∅ (definition of ∩)
iff enc(M ) ∈ Lne (definition of Lne ) .

Since there is no TM that always halts and that recognizes Lne , we can
conclude that L is not a recursive language.

Exercise 3.10 Provide answers to the following questions, together with

a mathematical proof for your statemets.

(i) Let L1 and L2 be two recursive languages. Is the language L1 L2 a

recursive language?

(ii) Let L1 be a recursive language and let L2 be a recursively enumerable

language. Is L1 ∩ L2 a recursive language?

(iii) Consider the language

L = {enc(M, M ′ ) | L(M ) ⊆ L(M ′ )}

where M, M ′ are generic TMs and enc(M, M ′ ) is an encoding of M, M ′ .

Is L a recursively enumerable language?

Solution Question 1: we show that the language L1 L2 is recursive. Since

L1 and L2 are recursive languages, there must exist two TM M1 and M2 that
halt for every possible input, and such that L(M1 ) = L1 and L(M2 ) = L2 .
Using M1 and M2 we can build a nondeterministic TM N that recognizes
the concatenation language L1 L2 . We will also show that N can be turned
into a deterministic TM that halts for every possible input string.
The TM N adopts the following strategy.

• Given a string w as input, N “guesses” nondeterministically a factor-

ization w = xy.

53
 • Next, N simulates M1 on the input string x, and simulates M2 on the
input string y.

• N halts and accepts if both M1 and M2 accept their respective inputs.

Otherwise, N stops and does not accept the input string w.

Let us first show the equivalence relation L1 L2 = L(N ), separately dis-

cussing the two parts L1 L2 ⊆ L(N ) and L(N ) ⊆ L1 L2 . By definition of the
concatenation operation, we have that if w ∈ L1 L2 then there exists at least
one pair of strings x, y such that xy = w, x ∈ L1 and y ∈ L2 . N will cer-
tainly guess the factorization xy = w. Furthermore, the simulation of both
machines M1 and M2 on x and y, respectively, end up in a final state, and
thus also N accepts. We have then w ∈ L(N ), and therefore L1 L2 ⊆ L(N ).
Let us now assume w ∈ L(N ). There exists a computation of N that
guesses a factorization w = xy, such that M1 and M2 halt on x and y,
respectively, both in a final state. This implies that x ∈ L1 and y ∈ L2 , and
by definition of concatenation we have w ∈ L1 L2 . Therefore L(N ) ⊆ L1 L2 .
Finally, we observe that all of the computations of N come to a halt.
Indeed, both TM M1 and M2 halt for every possible input, since the lan-
guages associated with the two TMs are recursive. In addition, the possible
ways to split a string w into two parts are |w|+1. In this case therefore we
can transform N into a deterministic TM M with L(N ) = L(M ), using the
technique studied in the textbook, and we are guaranteed that even M halts
for every possible input. We conclude therefore that the language L1 L2 is
recursive.
Question 2: we show that the language L1 ∩ L2 may not be recursive. To
prove this, it is sufficient to show a counterexample. Consider the language
L1 = Σ∗ , which is a regular language and therefore also a recursive language.
Consider also the language L2 = Lu , which is a well-known recursively
enumerable language but not recursive. We have L1 ∩ L2 = Lu which, as
already stated, is not a recursive language.
Question 3: we show that the language L is not a recursively enumerable
language (RE). To prove this, we provide a reduction from a language not in
RE to L. As a language not in RE we choose the following language, which
has been presented in the textbook

Le = {enc(M ′′ ) | L(M ′′ ) = ∅}.

The reduction takes as input an instance of Le , enc(M ′′ ), and builds an in-

stance of L, enc(M, M ′ ), such that enc(M ′′ ) ∈ Le if and only if enc(M, M ′ ) ∈
L. The construction of enc(M, M ′ ) is defined below.

54
 • We set M = M ′′

• We set M ′ = Me , where Me is any TM that accepts the empty lan-

guage.
We now prove that the proposed construction is a valid reduction, that
is, enc(M ′ ) ∈ Le if and only if enc(M, M ′ ) ∈ L.
(Only if part) If enc(M ′′ ) ∈ Le , then L(M ′′ ) = ∅. Consequently, we
have L(M ) = L(M ′ ) = ∅, and therefore L(M ) ⊆ L(M ′ ). This allows us to
conclude that enc(M, M ′ ) ∈ L.
(If part) If enc(M ′′ ) ̸∈ Le , then L(M ′′ ) ̸= ∅. Therefore we have L(M ) ̸⊆
L(M ′ ), and then enc(M, M ′ ) ̸∈ L.
The reduction allows us to conclude that the recognition of the language
L is at least as complex as the recognition of the language Le . Since we
know that Le does not belong to RE, we must conclude that L is not in RE
as well.

Exercise 3.11 Consider the language

L = {enc(M, w) | w ̸∈ L(M )}

where enc(M, w) is a binary string encoding the TM M and the binary

string w. Prove that L is not a recursively enumerable language.

Solution We observe upfront that the language defined in the exercise

is the complement of the universal language Lu defined in the textbook,
that is, L = Lu . Since we have seen that Lu is recursively enumerable but
not recursive, from a well-known theorem characterizing the complement of
recursively enumerable but not recursive languages, we have that Lu is not
recursively enumerable.
We can also directly prove that Lu is not recursively enumerable by
providing a reduction from Ld , the diagonal language defined in the textbook
as:

Ld = {wi | wi ∈
/ Mi }

where wi is the i-th string in the language {0, 1}∗ , according to the indexing
studied in the textbook, and Mi is the Turing machine whose encoding
enc(Mi ) is wi .
To define our reduction, let us consider a string w which represents an
instance of the decision problem associated with Ld . We specify a Turing

55
machine that, on input w, finds the index i such that wi = w, and returns
as output the string enc(Mi , wi ) where, as already mentioned, Mi is the TM
whose binary code is wi .
To conclude our proof we must show that the construction is a valid
reduction, that is, we must show that w ∈ Ld implies enc(Mi , wi ) ∈ Lu , and
enc(Mi , wi ) ∈ Lu implies w ∈ Ld . We have the following chain of logical
equivalences

w ∈ Ld iff w = wi ̸∈ L(Mi ) (definition of Ld )

iff enc(Mi , wi ) ̸∈ Lu (definition of Lu )
iff enc(Mi , wi ) ∈ Lu (definition of complement operator).

Since there is no TM that can recognize Ld , we conclude that there is no

Turing machine for Lu either, and then Lu is not a recursively enumerable
language.

Exercise 3.12 Consider the language

L = {enc(M1 , M2 , M3 ) | L(M1 ) ∩ L(M2 ) ̸= L(M3 ), }

where M1 , M2 and M3 are generic TMs, and where enc(M1 , M2 , M3 ) rep-

resents an appropriate encoding of these machines. Prove that L is not a
recursive language.

Solution We have already proved in Exercise 3.9 that the language L′ =

{enc(M, M ′ ) | L(M ) ∩ L(M ′ ) ̸= ∅} is not a recursive language. To solve
the present exercise, then, we can provide a reduction from L′ to L, proving
therefore that if there were a TM that always halts and recognizes L, then
there would be a TM that always halts and recognizes L′ , which contradicts
the findings of Exercise 3.9.
To construct our reduction we operate as follows. Let enc(M, M ′ ) be an
input instance for L′ , that is, a string for which we must verify membership
in L′ . We need to provide an instance enc(M1 , M2 , M3 ) and show that the
construction is indeed a valid reduction. We set M1 = M , M2 = M ′ .
Furthermore for M3 we take and TM that accepts the empty set. At this
point we have

enc(M, M ′ ) ∈ L′ iff L(M ) ∩ L(M ′ ) ̸= ∅ (definition of L′ )

iff L(M1 ) ∩ L(M2 ) ̸= L(M3 ) (definition of M3 )
iff enc(M1 , M2 , M3 ) ∈ L (definition of L).

56
This shows that our construction is a valid reduction, and concludes the
solution of the exercise.
As an alternatively solution, we can reduce Lu to L as follows. Let
enc(M, w) be an instance of the decision problem associated with Lu . Let
also M∅ be a TM that recognizes the empty language, and let Mw be a TM
that recognizes the language {w}, i.e. a language consisting only of the string
w. We can map the instance enc(M, w) into the instance enc(M, Mw , M∅ ).
It is immediately evident that

{w}, if w ∈ L(M )
L(M ) ∩ L(Mw ) =
∅, if w ̸∈ L(M )

Since {w} ̸= ∅ is always true, we can conclude that enc(M, w) ∈ Lu if and

only if enc(M, Mw , M∅ ) ∈ L, which proves that the presented construction
is indeed a valid reduction. Finally, since we know that Lu is not a recursive
language, we obtain that even L is not a recursive language.

57