Information Technology Reference
In-Depth Information
and
(an analogous definition can be given for the
right derivation
, by replacing prefixes by suffixes).
A (formal)
language
L
over an alphabet
A
is a set of strings over this alphabet,
that is,
L
∂
α
(
β
)=
λ
if
α
is not a prefix of
β
. Of course, the alphabet
A
is a language over
A
,
A
∗
is also a
language over
A
, and any finite (or empty) subset of
A
∗
is a language over
A
.
For example, all the strings over an alphabet
A
of length equal to or smaller than
n
define a (finite) language over the alphabet
A
:
A
∗
)
∈
P(
A
∗
||
α
|≤
{
α
∈
n
}
The following are languages over an alphabet
A
:
A
∗
}
{
αα
|
α
∈
A
∗
|
α
=
β
n
A
∗
,
{
α
∈
for any
β
∈
n
∈
N
}
A
∗
provides the following languages:
Any string
α
∈
A
∗
}
Pre f
(
α
)=
{
β
|
βγ
=
α
,
γ
∈
A
∗
}
Su f
(
α
)=
{
β
|
γβ
=
α
,
γ
∈
Sub
(
α
)=
{
β
|
β
⊆
α
}
If
is an operation defined on strings over an alphabet
A
, then we can extend it to
any language
L
over
A
by putting:
ω
ω
(
L
)=
{
ω
(
α
)
|
α
∈
L
}.
The definition of languages as particular sets, allows us to apply to them all the usual
boolean operation on set (union, intersection, and difference). However, the catena-
tive nature of strings provides other natural operations. Table 6.1 reports the main
operations on languages, where
L
1
,
A
∗
)
. In the context of formal languages,
for reasons of similarity with the notation that will be introduced, set-theoretic union
will be also called
sum
and will be denoted by
L
2
∈
P(
+
.
L
.
A
language expression
E
is constructed by applying language operations on
some initially given languages. A
grammar
G
for a language
L
is an algorithm
Abbreviation
α
L
stands for
{
α
}·
L
and
α
+
L
stands for
{
α
}
+
Ta b l e 6 . 1
Operations on languages
L
1
+
L
2
=
{
α
|
α
∈
L
1
,
or
α
∈
L
2
}
language sum
L
1
−
L
2
=
{
α
|
α
∈
L
1
,
α
∈
L
2
}
language difference
L
1
∩
L
2
=
{
α
|
α
∈
L
1
,
α
∈
L
2
}
language intersection
L
1
·
L
2
=
{
αβ
|
α
∈
L
1
,
β
∈
L
2
}
language concatenatiion
L
n
=
{
α
1
α
2
...
α
n
|
α
i
∈
L
,
for
i
=
1
,
2
,...,
n
}
language iteration (
n
≥
1
)
L
∗
=
{
α
1
α
2
...
α
n
|
α
i
∈
L
,
for
i
=
1
,
2
,...,
n
,
and
n
∈
N
}
Kleene star
