Information Technology Reference
In-Depth Information
bababaccb
.
If
R
is a set of string rewriting rules, over some alphabet, and
L
a language over the
same alphabet, then the language
R
∗
(
)
, generated by
R
from
L
,isdefinedasthe
minimum language including
L
and
closed
with respect to the rules of
R
. This means
that, when
R
∗
(
L
)
contains some strings, then it contains also the strings obtained
from them by means of an application of a rule of
R
.
It can be shown that the language
R
∗
(
L
can be generated by applying the rules of
R
to strings of
L
by means of
string derivations
. A string derivation is a sequence
of steps, where in the initial step some strings of
L
are chosen, and in every follow-
ing step strings are generated that are either strings of
L
, or strings obtained by an
application of a rule of
R
to strings generated at preceding steps.
Figure 6.5 represents a string derivation by means of rules with two premises and
two conclusions, by means of a suitable tree (with leaves on the top and the root on
the bottom).
Consider the following rule (
x
L
)
}
∗
):
,
y
∈{
a
,
b
,
c
xaby
xaabbyc
r
=
it is easy to verify that:
a
n
b
n
c
n
}
∗
(
{
L(
)=
{
r
abc
}
)
.
In fact, when the rule is applied to a string of the tri-somatic language, then it pro-
vides a string which follows the same pattern. Therefore, starting from the shortest
string of this type (we do not consider string
λ
), we are able to provide any possible
Fig. 6.5
A string derivation represented as a tree
