Information Technology Reference
In-Depth Information
a | a
q
q
q
e
q
o
b | b
a |
b | bb
a | aa
a |
(a)
f
del
(b)
f
double
(c)
f
1
/
2
Fig. 2.
Examples of finite state transducers
denoted by
O
(
r
), is defined as the word
O
(
r
)=
v
1
...v
n
.Therun
r
is
accepting
if
p
n
∈
F
.
An FST
T
realises a functional transformation
T
:
ʣ
∗
→
ʣ
∗
defined by
T
=
{
(
u,v
)
|
there exists an accepting run
r
of
T
on
u
such that
v
=
O
(
r
)
}
Note that indeed, since
T
is deterministic,
is a function. The extension of
FST with non-determinism allows one to define relations instead of functions.
A
non-deterministic finite state transducer
(NFT) over an alphabet
ʣ
is a
tuple
T
=(
Q,q
0
,F,ʔ
)where
Q,q
0
,F
are defined as for FST, and
ʔ
:
Q
T
×
ʣ
×
ʣ
∗
is a (partial) function that defines the transitions
2
.Arunof
T
is defined
similarly as a run of an FST, as a sequence
r
=
p
0
˃
1
p
1
...˃
n
p
n
such that
p
0
=
q
0
and for all
i
Q
→
ʣ
∗
.The
output
O
(
r
) is defined by
O
(
r
)=
v
1
...v
n
. The other notions defined for FST
carry over to NFT. Note that
∈{
1
,...,n
}
,
ʴ
(
p
i−
1
,˃
i
,p
i
) exists and is equal to some
v
i
∈
may not be a function, since there can be
several accepting runs on an input word. However, whether an NFT defines a
function is decidable in
PTime
(see, for instance, [7]). NFT defining functions
are known as
functional NFT
.
T
Example 4.
Fig. 2 illustrates three FST that define the functions
f
del
,
f
double
and
f
1
/
2
respectively. On these figures, the vertical arrow represents the initial
state, the double circles the accepting states, and the arrows labelled
˃
|
v
the
ʣ
∗
. The other functions,
f
copy
,
f
rev
and
f
exp
are not definable by finite state transducers (even NFT). As we will
see in Section 5.3, any NFT-definable functional transformation is definable by
an MSO-transducer. We define in Section 5.3 a restriction on MSO-transducer
that captures exactly NFT-definable functions.
transitions that read
˃
∈
ʣ
and produce
v
∈
4.2 Two-Way Finite State Transducers
Two-way finite state transducers (2FST) extend (one-way) finite state transducer
with a bidirectional input head. Depending on the current state and letter, a
2FST updates its internal state and moves its input head either left or right. In
order to detect the first and last positions of the input word, 2FST are assumed
to run on words that are nested with begin and end markers
,
respectively.
2
These NFT are sometimes called
real-time
NFT, in contrast to a more general class
of NFT that allow productive
-transitions.
