Information Technology Reference
In-Depth Information
which generates all and only the strings of
L
.An
automaton
M
for
L
is an algorithm
which recognizes all and only the strings of
L
.Astring
pattern
P
is a linear structure
(represented by an algebraic expression, as we see later on) which is common to all
the strings of
L
.
We will denote by
L(
)
,
L(
)
,
L(
)
,
L(
)
the language specified by the gram-
mar
G
, by the automaton
M
, and by the pattern
P
respectively. A typical problem of
formal language theory is the passage from one method of specification of a given
language, to another method which specifies the same language.
The intuition behind a grammar is that of a set of rules for writing words (syntac-
tic forms). An automation can be seen as a device which, when it takes a symbolic
form as an input, it answers yes/not in correspondence of a recognized/unrecognized
structure. The term
pattern
comes from Latin
paternitas
and expresses an origin
which is common to all the strings with a specific
imprinting
. These strings are said
to be
instances
of the pattern. In formal terms, a pattern (of strings) can be defined
as an expression built by means of string operations, from some strings, and vari-
ables ranging in some specific sets, and/or satisfying some conditions. When values
are given to the variables of a pattern
P
, the corresponding values that
P
assume are
the strings of
E
G
M
P
.
An analogy can be useful to clarify the notion of (string) pattern. In fact, a poly-
nomial with positive integer coefficients and positive integer variables can be con-
sidered a number pattern. For example,
L(
P
)
3
x
+
4
y
is a pattern such that number 10 is an instance of it, in correspondence to the values
x
=
2
,
y
=
1, but 5 is not an instance of this pattern because the equation 3
x
+
4
y
=
5
,
does not hold for any pair of positive integer values of
x
y
. Analogously, the string
A
∗
has the string
abb
as its instance, but the string
aab
cannot
∈
pattern
axx
with
x
be an instance of it.
The following language is constructed by starting from languages
{
a
}
and
{
b
}
by Kleene star and language concatenation:
}
∗
.
The same language is specified by the pattern
a
n
b
m
with
n
}
∗
·{
{
a
b
,
m
∈
N
.
}
respectively) are the following, where term
soma
(meaning body in Greek) refers to
their interpretations, as growing structures (of one, two, or three components):
Some important patterns defining languages (over alphabets
{
a
,
b
}
and
{
a
,
b
,
c
a
n
Mono-somatic Pattern
=
with
n
∈
N
,
n
>
0
a
n
b
n
Bi-somatic Pattern
=
with
n
∈
N
,
n
>
0
a
n
b
n
c
n
Tri-somatic Pattern
=
with
n
∈
N
,
n
>
0
.
