Motivation

Background

Relations

Languages

Palindromes

End

Theory of Computation
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
http://www-alg.ist.hokudai.ac.jp/∼thomas/ToC/

Lecture 1: Introducing Formal Languages

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation I

This course is about the study of a fascinating and important
subject:
the theory of computation.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation I

This course is about the study of a fascinating and important
subject:
the theory of computation.
It comprises the fundamental mathematical properties ofcomputer hardware, software, and certain applications thereof.
We are going to determine what can and cannot be computed.
If it can, we also seek to figure out on which type ofcomputational model, how quickly, and with how muchmemory.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation II

Theory of computation has many connections with engineering
practice, and, as a true science, it also comprises philosophicalaspects.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation II

Theory of computation has many connections with engineering
practice, and, as a true science, it also comprises philosophicalaspects.
Since formal languages are of fundamental importance tocomputer science, we shall start our course by having a closer
look at them.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation II

Theory of computation has many connections with engineering
practice, and, as a true science, it also comprises philosophicalaspects.
Since formal languages are of fundamental importance tocomputer science, we shall start our course by having a closer
look at them.
First, we clarify the subject of formal language theory.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation III

Generally speaking, formal language theory concerns itself
with sets of strings called languages and different mechanisms
for generating and recognizing them. Mechanisms forgenerating sets of strings are usually referred to as grammars
and mechanisms for recognizing sets of strings are called
acceptors or automata.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation III

Generally speaking, formal language theory concerns itself
with sets of strings called languages and different mechanisms
for generating and recognizing them. Mechanisms forgenerating sets of strings are usually referred to as grammars
and mechanisms for recognizing sets of strings are called
acceptors or automata.
A mathematical theory for generating and accepting languages
emerged in the later 1950’s and has been extensively developedsince then. Nowadays there are elaborated theories for bothcomputer languages and natural languages.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation IV

We have to restrict ourselves to the most fundamental parts offormal language theory, i.e., to the regular languages, thecontext-free languages, and the recursively enumerable
languages. This will suffice to obtain a basic understanding ofwhat formal language theory is all about and what are thefundamental proof techniques.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Motivation IV

We have to restrict ourselves to the most fundamental parts offormal language theory, i.e., to the regular languages, thecontext-free languages, and the recursively enumerable
languages. This will suffice to obtain a basic understanding ofwhat formal language theory is all about and what are thefundamental proof techniques.
For having a common ground, we shortly recall themathematical background needed.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background I

For any set M, by card(M) and ℘(M) we denote the cardinalityof M and the power set of M, respectively.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background I

For any set M, by card(M) and ℘(M) we denote the cardinalityof M and the power set of M, respectively.
Let X, Y be any two sets; then we use X ∪ Y, X ∩ Y and X \ Y todenote the union, intersection and difference of X and Y,
respectively.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background I

For any set M, by card(M) and ℘(M) we denote the cardinalityof M and the power set of M, respectively.
Let X, Y be any two sets; then we use X ∪ Y, X ∩ Y and X \ Y todenote the union, intersection and difference of X and Y,
respectively.
Furthermore, we denote the empty set by ∅.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background I

For any set M, by card(M) and ℘(M) we denote the cardinalityof M and the power set of M, respectively.
Let X, Y be any two sets; then we use X ∪ Y, X ∩ Y and X \ Y todenote the union, intersection and difference of X and Y,
respectively.
Furthermore, we denote the empty set by ∅.
By N = {0, 1, 2, . . .} we denote the set of all natural numbers. We
set N+ = N \ {0}.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background II

If
S we have countably many sets X0 , X1 , . . . , then we usei∈N Xi to denote the union of all Xi , i.e.,
[

Xi

=

X0 ∪ X1 ∪ · · · ∪ Xn ∪ · · · .

(1)

i∈N

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background II

If
S we have countably many sets X0 , X1 , . . . , then we usei∈N Xi to denote the union of all Xi , i.e.,
[

Xi

=

X0 ∪ X1 ∪ · · · ∪ Xn ∪ · · · .

(1)

i∈N

T
Analogously, we write i∈N Xi to denote the intersection of
all Xi , i.e.,\
Xi = X0 ∩ X1 ∩ · · · ∩ Xn ∩ · · · .
(2)i∈NTheory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background III
It is useful to have the following notions: Let X, Y be any sets
and let f : X → Y be a function. For any y ∈ Y we define
f−1 (y) = {x | x ∈ X, f(x) = y} .

(3)

We refer to f−1 (y) as to the set of pre-images of y.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background III
It is useful to have the following notions: Let X, Y be any sets
and let f : X → Y be a function. For any y ∈ Y we define
f−1 (y) = {x | x ∈ X, f(x) = y} .

(3)

We refer to f−1 (y) as to the set of pre-images of y.
Also, we need the following definition:
Definition 1
Let X, Y be any sets and let f : X → Y be a function. The
function f is said to be(1) injective if f(x) = f(y) implies x = y for all x, y ∈ X;(2) surjective if for every y ∈ Y there is an x ∈ X such thatf(x) = y;(3) bijective if f is injective and surjective.
Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background IV
Next, let X and Y be any sets. We say that X and Y have the same
cardinality if there exists a bijection f : X → Y. If a set X has thesame cardinality as the set N of natural numbers, then we saythat X is countably infinite.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background IV
Next, let X and Y be any sets. We say that X and Y have the same
cardinality if there exists a bijection f : X → Y. If a set X has thesame cardinality as the set N of natural numbers, then we saythat X is countably infinite.
A set X is at most countably infinite if it is finite or countably
infinite. If X , ∅ and X is at most countably infinite, then there
exists a surjection f : N → X, i.e.,
X = {f(0), f(1), f(2), . . .} .
So, intuitively, we can enumerate all the elements of X (whererepetitions are allowed).

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background V
The following theorem is of fundamental importance:
Theorem 1 (Cantor’s Theorem)
For every countably infinite set X the set ℘(X) is not countably
infinite.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background V
The following theorem is of fundamental importance:
Theorem 1 (Cantor’s Theorem)
For every countably infinite set X the set ℘(X) is not countably
infinite.
Since X is countably infinite, there is a bijection f : N → X.
Suppose that ℘(X) is countably infinite. Then there must exist abijection g : N → ℘(X).

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background V
The following theorem is of fundamental importance:
Theorem 1 (Cantor’s Theorem)
For every countably infinite set X the set ℘(X) is not countably
infinite.
Since X is countably infinite, there is a bijection f : N → X.
Suppose that ℘(X) is countably infinite. Then there must exist abijection g : N → ℘(X).
Now, we define a diagonal set D as follows:
D = {f(j) | j ∈ N, f(j) < g(j)} .
By construction, D ⊆ X and hence D ∈ ℘(X). Consequently,
there must be a number d ∈ N such that D = g(d).
Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background VI

Now, we consider f(d). By the definition of f we know thatf(d) ∈ X. Since D ⊆ X, there are two possible cases, eitherf(d) ∈ D or f(d) < D.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background VI

Now, we consider f(d). By the definition of f we know thatf(d) ∈ X. Since D ⊆ X, there are two possible cases, eitherf(d) ∈ D or f(d) < D.
Case 1. f(d) ∈ D.
By the definition of D and d we directly getf(d) ∈ D ⇐⇒ f(d) < g(d) ⇐⇒ f(d) < D ,since g(d) = D. This contradiction shows that Case 1 cannot
happen.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Background VII

Case 2. f(d) < D.
Again, by construction, f(d) < D holds if and only if f(d) ∈ g(d)if and only if f(d) ∈ D, again a contradiction.
Thus, Case 2 cannot happen either, and hence the supposition
that ℘(X) is countably infinite, cannot hold.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations I

Let X, Y be any non-empty sets. We set
X × Y = {(x, y) | x ∈ X and y ∈ Y}.
Every ρ ⊆ X × Y is said to be a binary relation.
We sometimes use the notation xρy instead of writing(x, y) ∈ ρ. Of special importance is the case where X = Y. If
ρ ⊆ X × X then we also say that ρ is a binary relation over X.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations II
Definition 2
Let X , ∅ be any set, and let ρ be any binary relation over X.
The relation ρ is said to be(1) reflexive if (x, x) ∈ ρ for all x ∈ X;(2) symmetric if (x, y) ∈ ρ implies (y, x) ∈ ρ for all x, y ∈ X;(3) transitive if (x, y) ∈ ρ and (y, z) ∈ ρ implies (x, z) ∈ ρ forall x, y, z ∈ X;(4) antisymmetric if (x, y) ∈ ρ and (y, x) ∈ ρ implies x = y for
all x, y, z ∈ X.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations II
Definition 2
Let X , ∅ be any set, and let ρ be any binary relation over X.
The relation ρ is said to be(1) reflexive if (x, x) ∈ ρ for all x ∈ X;(2) symmetric if (x, y) ∈ ρ implies (y, x) ∈ ρ for all x, y ∈ X;(3) transitive if (x, y) ∈ ρ and (y, z) ∈ ρ implies (x, z) ∈ ρ forall x, y, z ∈ X;(4) antisymmetric if (x, y) ∈ ρ and (y, x) ∈ ρ implies x = y for
all x, y, z ∈ X.
Any binary relation satisfying (1) through (3) is called
equivalence relation. For any x ∈ X, we write [x] to denote theequivalence class generated by x, i.e.,[x] = {y | y ∈ X and (x, y) ∈ ρ} .
Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations III
Any relation satisfying (1), (3) and (4) is called partial order. In
this case, we also say that (X, ρ) is a partially ordered set.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations III
Any relation satisfying (1), (3) and (4) is called partial order. In
this case, we also say that (X, ρ) is a partially ordered set.
Definition 3
Let ρ ⊆ X × Y and τ ⊆ Y × Z be binary relations. The
composition of ρ and τ is the binary relation ζ ⊆ X × Z defined
as
ζ

=

ρτ

=

{(x, z) | there is a y ∈ Y such that (x, y) ∈ ρ, (y, z) ∈ τ} .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations IV
Now, let X , ∅ be any set; there is a special binary relation ρ0called equality, and defined as ρ0 = {(x, x) | x ∈ X}.
Moreover, let ρ ⊆ X × X be any binary relation. We inductively
define ρi+1 = ρi ρ for each i ∈ N.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations IV
Now, let X , ∅ be any set; there is a special binary relation ρ0called equality, and defined as ρ0 = {(x, x) | x ∈ X}.
Moreover, let ρ ⊆ X × X be any binary relation. We inductively
define ρi+1 = ρi ρ for each i ∈ N.
Definition 4
Let X , ∅ be any set, and ρ be any binary relation over X. The
reflexive-transitive
closure of ρ is the binary relationSρ∗ = i∈N ρi .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Relations IV
Now, let X , ∅ be any set; there is a special binary relation ρ0called equality, and defined as ρ0 = {(x, x) | x ∈ X}.
Moreover, let ρ ⊆ X × X be any binary relation. We inductively
define ρi+1 = ρi ρ for each i ∈ N.
Definition 4
Let X , ∅ be any set, and ρ be any binary relation over X. The
reflexive-transitive
closure of ρ is the binary relationSρ∗ = i∈N ρi .
Next, we introduce a formalism to deal with strings and sets ofstrings.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Alphabets

By Σ we denote a finite non-empty set called alphabet. The
elements of Σ are assumed to be indivisible symbols and referred
to as letters or symbols.
Examples:Σ = {0, 1} is an alphabet containing the letters 0 and 1, andΣ = {a, b, c} is an alphabet containing the letters a, b, and c.
In compiling, we may also have alphabets containing forexample begin and end. But the letters begin and end are also
assumed to be indivisible.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Alphabets

By Σ we denote a finite non-empty set called alphabet. The
elements of Σ are assumed to be indivisible symbols and referred
to as letters or symbols.
Examples:Σ = {0, 1} is an alphabet containing the letters 0 and 1, andΣ = {a, b, c} is an alphabet containing the letters a, b, and c.
In compiling, we may also have alphabets containing forexample begin and end. But the letters begin and end are also
assumed to be indivisible.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Alphabets

By Σ we denote a finite non-empty set called alphabet. The
elements of Σ are assumed to be indivisible symbols and referred
to as letters or symbols.
Examples:Σ = {0, 1} is an alphabet containing the letters 0 and 1, andΣ = {a, b, c} is an alphabet containing the letters a, b, and c.
In compiling, we may also have alphabets containing forexample begin and end. But the letters begin and end are also
assumed to be indivisible.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Strings

Definition 5
A string over an alphabet Σ is a finite length sequence of lettersfrom Σ. A typical string is written as s = a1 a2 · · · ak , whereai ∈ Σ for i = 1, . . . , k.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Strings

Definition 5
A string over an alphabet Σ is a finite length sequence of lettersfrom Σ. A typical string is written as s = a1 a2 · · · ak , whereai ∈ Σ for i = 1, . . . , k.
Note that we also allow k = 0 resulting in the empty string
which we denote by λ. We call k the length of s and denote it
by |s|, so |λ| = 0. By Σ∗ we denote the set of all strings over Σ,and we set Σ+ = Σ∗ \ {λ}.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Concatenation

Let s, w ∈ Σ∗ ; we define a binary operation called concatenation(or word product). The concatenation of s and w is the string sw.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Concatenation

Let s, w ∈ Σ∗ ; we define a binary operation called concatenation(or word product). The concatenation of s and w is the string sw.
Example: Let Σ = {0, 1}, s = 000111 and w = 0011;
then sw = 0001110011.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Properties of Concatenation
Proposition 1
Let Σ be any alphabet.
(1) Concatenation is associative, i.e., for all x, y, z ∈ Σ∗ ,x(yz) = (xy)z .
(2) The empty string λ is a two-sided identity for Σ∗ , i.e., for allx ∈ Σ∗ ,xλ = λx = x .
(3) Σ∗ is free of nontrivial identities, i.e., for all x, y, z ∈ Σ∗ ,i) zx = zy implies x = y and,ii) xz = yz implies x = y .

(4) For all x, y ∈ Σ∗ , |xy| = |x| + |y|.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Extension to Sets of Strings
Let X, Y be sets of strings. Then the product of X and Y is
defined as
XY = {xy | x ∈ X and y ∈ Y}.
Let X ⊆ Σ∗ ; define X0 = {λ} and for allSi > 0 set Xi+1 = Xi X. The
Kleene closure of X is defined asSX∗ = i∈N Xi , and thesemigroup closure of X is X+ = i∈N+ Xi .
Finally, we define the transpose of a string and of sets of strings.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Extension to Sets of Strings
Let X, Y be sets of strings. Then the product of X and Y is
defined as
XY = {xy | x ∈ X and y ∈ Y}.
Let X ⊆ Σ∗ ; define X0 = {λ} and for allSi > 0 set Xi+1 = Xi X. The
Kleene closure of X is defined asSX∗ = i∈N Xi , and thesemigroup closure of X is X+ = i∈N+ Xi .
Finally, we define the transpose of a string and of sets of strings.
Definition 6
Let Σ be any alphabet. The transpose operator is defined on
strings in Σ∗ and on sets X ⊆ Σ∗ of strings as follows:
λT
T

(xa)

XT
Theory of Computation

= λ,

and

= a(x ) for all x ∈ Σ∗ and all a ∈ ΣT= {xT | x ∈ X} .
c Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Languages I

Definition 7
Let Σ be any alphabet. Every subset L ⊆ Σ∗ is called language.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Languages I

Definition 7
Let Σ be any alphabet. Every subset L ⊆ Σ∗ is called language.
Note that the empty set as well as L = {λ} are also languages.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Languages I

Definition 7
Let Σ be any alphabet. Every subset L ⊆ Σ∗ is called language.
Note that the empty set as well as L = {λ} are also languages.
Next, we ask how many languages there are. Let m be thecardinality of Σ. There is precisely one string of length 0, i.e., λ,there are m strings of length 1, i.e., a for all a ∈ Σ, there are m2
many strings of length 2, and in general there are mn many
strings of length n. Thus, the cardinality of Σ∗ is countably
infinite.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

PalindromesEnd

Languages II

By Cantor’s theorem we know that card(M) < card(℘(M)). So,
we can conclude that there are uncountably many languages(as much as there are real numbers).
Since the generation and recognition of languages should bedone algorithmically, we immediately see that only countably
many languages can be generated and recognized by analgorithm.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes I

A palindrome is a string that reads the same from left to rightand from right to left, e.g.,
AKASAKA

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes I

A palindrome is a string that reads the same from left to rightand from right to left, e.g.,
AKASAKA
ddddddd
ddddddddddd
dddddddddd

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes I

A palindrome is a string that reads the same from left to rightand from right to left, e.g.,
AKASAKA
ddddddd
ddddddddddd
dddddddddd
Now we ask how can we describe the language of all
palindromes over the alphabet {a, b} (just to keep it simple).

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes II
So let us try it. Of course λ, a, and b are palindromes. Everypalindrome must begin and end with the same letter, and if weremove the first and last letter of a palindrome, we still get apalindrome. This observation suggests the following basis andinduction for defining Lpal :Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes II
So let us try it. Of course λ, a, and b are palindromes. Everypalindrome must begin and end with the same letter, and if weremove the first and last letter of a palindrome, we still get apalindrome. This observation suggests the following basis andinduction for defining Lpal :Induction Basis: λ, a, and b are palindromes.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes II
So let us try it. Of course λ, a, and b are palindromes. Everypalindrome must begin and end with the same letter, and if weremove the first and last letter of a palindrome, we still get apalindrome. This observation suggests the following basis andinduction for defining Lpal :Induction Basis: λ, a, and b are palindromes.
Induction Step: If w ∈ {a, b}∗ is a palindrome, then awa andbwb are also palindromes. Furthermore, no string w ∈ {a, b}∗ isa palindrome, unless it follows from this basis and induction
step.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes II
So let us try it. Of course λ, a, and b are palindromes. Everypalindrome must begin and end with the same letter, and if weremove the first and last letter of a palindrome, we still get apalindrome. This observation suggests the following basis andinduction for defining Lpal :Induction Basis: λ, a, and b are palindromes.
Induction Step: If w ∈ {a, b}∗ is a palindrome, then awa andbwb are also palindromes. Furthermore, no string w ∈ {a, b}∗ isa palindrome, unless it follows from this basis and induction
step.
But stop, we could have also used the transpose operator T todefine the language of all palindromes, i.e.,L̃pal = {w ∈ {a, b}∗ | w = wT } .
Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes III

We used a different notation in the latter definition, since westill do not know whether or not Lpal = L̃pal . For getting thisequality, we need a proof.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes III

We used a different notation in the latter definition, since westill do not know whether or not Lpal = L̃pal . For getting thisequality, we need a proof.
Theorem 2
Lpal = L̃pal .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes III

We used a different notation in the latter definition, since westill do not know whether or not Lpal = L̃pal . For getting thisequality, we need a proof.
Theorem 2
Lpal = L̃pal .
Proof. Equality of sets X, Y is often proved by showing X ⊆ Y
and Y ⊆ X. So, let us first show that Lpal ⊆ L̃pal .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes IV
We start with the strings defined by the basis, i.e., λ, a, and b.
By the definition of the transpose operator, we have λT = λ.
Thus, λ ∈ L̃pal . Next, we deal with a. In order to apply thedefinition of the transpose operator, we use Property (2) of
Proposition 1, i.e., a = λa. Then, we haveaT = (λa)T = aλT = aλ = a .
The proof for b is analogous and thus omitted.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes IV
We start with the strings defined by the basis, i.e., λ, a, and b.
By the definition of the transpose operator, we have λT = λ.
Thus, λ ∈ L̃pal . Next, we deal with a. In order to apply thedefinition of the transpose operator, we use Property (2) of
Proposition 1, i.e., a = λa. Then, we haveaT = (λa)T = aλT = aλ = a .
The proof for b is analogous and thus omitted.
Now, the induction hypothesis is that for all strings w with|w| 6 n, we have w ∈ Lpal implies w ∈ L̃pal . In accordance with
our definition of Lpal , the induction step is from n to n + 2. Letw ∈ Lpal be any string with |w| = n + 2. Thus, w = ava or
w = bvb, where v ∈ {a, b}∗ such that |v| = n. Then v is apalindrome in the sense of the definition of Lpal , and by the
induction hypothesis, we know that v = vT .
Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes V
The following claims provide a special property of thetranspose operator:
Claim 1. Let Σ be any alphabet, n ∈ N+ , and w = w1 . . . wn ∈ Σ∗ ,where wi ∈ Σ for all i ∈ {1, . . . , n}. Then wT = wn . . . w1 .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes V
The following claims provide a special property of thetranspose operator:
Claim 1. Let Σ be any alphabet, n ∈ N+ , and w = w1 . . . wn ∈ Σ∗ ,where wi ∈ Σ for all i ∈ {1, . . . , n}. Then wT = wn . . . w1 .
Claim 2. For all n ∈ N, if p = p1 xpn+2 then pT = pn+2 xT p1 for all
p1 , pn+2 ∈ {a, b} and x ∈ {a, b}∗ , where |x| = n.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes V
The following claims provide a special property of thetranspose operator:
Claim 1. Let Σ be any alphabet, n ∈ N+ , and w = w1 . . . wn ∈ Σ∗ ,where wi ∈ Σ for all i ∈ {1, . . . , n}. Then wT = wn . . . w1 .
Claim 2. For all n ∈ N, if p = p1 xpn+2 then pT = pn+2 xT p1 for all
p1 , pn+2 ∈ {a, b} and x ∈ {a, b}∗ , where |x| = n.
Note that Claim 1 is needed to show Claim 2. The proofs areleft as exercise.
By using Claim 2 just established we get
wT = (ava)T = avT a |{z}= ava = w .
by IH

Again, the case w = bvb can be handled analogously and isthus omitted.
Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes VI

Finally, we have to show L̃pal ⊆ Lpal .
For the induction basis, we know that λ = λT , i.e., λ ∈ L̃pal andby the induction basis of the definition of Lpal , we also knowthat λ ∈ Lpal .
Thus, we have the induction hypothesis that for all strings w oflength n: if w = wT then w ∈ Lpal .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes VI

Finally, we have to show L̃pal ⊆ Lpal .
For the induction basis, we know that λ = λT , i.e., λ ∈ L̃pal andby the induction basis of the definition of Lpal , we also knowthat λ ∈ Lpal .
Thus, we have the induction hypothesis that for all strings w oflength n: if w = wT then w ∈ Lpal .
The induction step is from n to n + 1. That is, we have to show
if |w| = n + 1 and w = wT then w ∈ Lpal .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes VI

Finally, we have to show L̃pal ⊆ Lpal .
For the induction basis, we know that λ = λT , i.e., λ ∈ L̃pal andby the induction basis of the definition of Lpal , we also knowthat λ ∈ Lpal .
Thus, we have the induction hypothesis that for all strings w oflength n: if w = wT then w ∈ Lpal .
The induction step is from n to n + 1. That is, we have to show
if |w| = n + 1 and w = wT then w ∈ Lpal .
Since the case n = 1 directly results in a and b and sincea, b ∈ Lpal , we assume n > 1 in the following.

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes VII
So, let w ∈ {a, b}∗ be any string with |w| = n + 1 and w = wT ,say w = a1 . . . an+1 , where ai ∈ Σ. Thus, by assumption wehave
a1 . . . an+1 = an+1 . . . a1 .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Palindromes VII
So, let w ∈ {a, b}∗ be any string with |w| = n + 1 and w = wT ,say w = a1 . . . an+1 , where ai ∈ Σ. Thus, by assumption wehave
a1 . . . an+1 = an+1 . . . a1 .
Now, applying Property (3) of Proposition 1 directly yields
a1 = an+1 . We have to distinguish the cases a1 = a and a1 = b.
Since both cases can be handled analogously, we consider only
the case a1 = a here. Thus, we can conclude w = ava, wherev ∈ {a, b}∗ and |v| = n − 1. Next, applying the property of thetranspose operator established above, we obtain v = vT , i.e.,v ∈ Lpal . Finally, the “induction” part of the definition of Lpal
directly implies w ∈ Lpal .

Theory of Computationc Thomas Zeugmann

Motivation

Background

Relations

Languages

Palindromes

End

Thank you!

Theory of Computationc Thomas Zeugmann