Information Technology Reference
In-Depth Information
a
n
b
n
c
n
string of the language. The above generation of
L(
)
shows as powerful are
rewriting rules including variables.
In the case of replacement variables remain “fixed”, but when they are rearranged
in the conclusions, then a global transformation is applied to the input strings in
order to generate the output strings. This means that particular kinds of rewriting
rules can be very powerful, and few rules can generate languages which require
Chomsky grammars with greater numbers of rules. For example, consider a sort of
multiple rewriting expressed by the rule:
a
,
b
,
c
→
aa
,
bb
,
cc
that simultaneously rewrites any three occurrences of the three symbols by their dupli-
cates, according to the following formulation by means of patterns (
x
}
∗
):
,
y
∈{
a
,
b
,
c
axbyc
aaxbbycc
.
In this way, starting from the string
abc
the tri-somatic language is generated by
means of string derivations which use only this multiple rewriting.
6.5
Turing Machine
From a very general point of view, a computation system is defined by seven com-
ponents:
1. A set
D
of
data
;
2. a set
S
of
states
;
3. an
input function
(encoding data into states)
in
:
D
→
S
;
4. an
output function
(decoding states into data)
out
:
S
→
D
;
5. a set
Ω
of
operations
on the set
S
;
6. a set
Φ
of
rules
which are functions
ρ
:
S
→
P(
Ω
)
;
7. a set of
computations
which are sequences of states with an initial state en-
coding the initial data. For any state
s
a state
s
follows
s
in a computation if
s
=
ω
(
Γ
s
)
for some
ω
∈
ρ
(
s
)
. A computation halts with a
terminal
state
s
f
when
ρ
(
s
f
)=
0.
The previous structure describes a system where data are encoded by states and a
dynamics is defined on the states that ends when the system reaches final states
encoding results. In this sense, a computation is a special kind of dynamics where
the passage from a state to another is performed by applying one operation among
those which are applicable in a given state.
This general schema can be realized and extended in many ways. Namely, the
rule of applying operations can be external to the system, and at each step an opera-
tor can intervene in the system for its evolution. Otherwise, a description of this rule,
usually called
program
, can be internal to the system, by making it able to evolve
in a specific way. In this case the system is a
programmed
computation system,
