Information Technology Reference
In-Depth Information
Some regular expressions can be represented by patterns having only vari-
ables ranging on natural numbers. For example
a
∗
+
c
∗
)
b
(
can be represented by
a
n
c
m
(different occurrences of Kleene star deserve different
variables). Patterns built with strings, string operations, variables, and language op-
erations provide a very powerful way of expressing forms of strings. It can be proved
that suitable combinations of patterns with logical conditions on them provide an
expressive power equivalent to the Chomsky grammars of type 0 [204].
The notion of pattern is useful for giving a general definition of
string rewriting
rule
. The general idea of such a rule is that of a combinatorial rearrangement of
pieces of some input strings for producing some output strings. This can be repre-
sented by a sequence of patterns, called
premises
, and a sequence of patterns called
conclusions
, such that, in the conclusions variables occur that appear also in the
premises:
+
b
(
)
with
n
,
m
∈
N
Premises
Conclusions
.
According to this format, the grammatical rewriting relation has only one premise
and one conclusion, that is,
α
⇒
β
can be expressed in the following way, where
G
y
are variable over
A
∗
(
A
the alphabet of
G
):
x
,
x
α
y
y
.
x
β
This kind of rule is also called a
replacement
. In a string rewriting rule all the
variables occurring in the conclusions have to occur also in the premises, and have
to verify the same constraints.
For example, the following rule has two premises, one conclusion and two vari-
ables (
x
A
∗
):
,
y
∈
by
bxyb
.
A string rewriting rule can be
applied
to a sequence of strings when these strings
are instances of the premises, for suitable values of their variables. In this case, the
application of the rule yields the evaluation of the conclusions, according to the
same values of variables assigned to the variables of premises.
The rule given above can be applied to the strings:
xb
,
ababab
,
bcc
according to the following values of premise variables:
x
=
ababa
y
=
cc
and provides as a conclusion the following instance:
