Information Technology Reference
In-Depth Information
Platonic Dodecahedron
6
Languages and Grammars
Abstract.
Strings are sequences on which some specific operations are defined. The
most important operation over strings is the
concatenation
.If
α
and
β
are two
strings, their concatenation, usually denoted by
αβ
, is the sequence where the last
element of
.
Formal
languages
are sets of strings. In this chapter we present some basic concepts of
formal language theory: languages, grammars, automata, expressions, and patterns.
We conclude by outlining the notions of decidability and undecidability, and with
two famous kinds of computation automata: Turing machines and register machines.
α
is followed by the elements of
β
, in the order they have in
β
6.1
Strings and Languages
Formal language theory (FLT) started at the beginning of the 20th century with
some seminal papers by Thue [195], where strings are considered as mathematical
objects defining the algebraic structure of
monoid
, based on the binary operation
of concatenation (juxtaposition of strings) that is associative. When the theory of
computation (and computability) started and symbolic processes were investigated
in mathematical terms [214, 208, 209, 196, 197, 203], then formal languages, as sets
of strings, and classes of formal languages proved to be crucial for a wide class of
concepts that became of fundamental importance for computer science [201, 199,
206, 210, 211, 213].
Given an alphabet
A
, we denote by
A
∗
the set of finite sequences of symbols of
A
equipped by the operation of
concatenation
such that, if:
α
=
α
,
α
,...,
α
1
2
n
β
=
β
,
β
,...,
β
1
2
m
