F. Song, W. Miao, G. Pu, and M. Zhang 385
2 Preliminaries
2.1 Finite-State Transducers and Transduction
I Definition 1.
A finite-state transducer (FST)
T
is a tuple (
Q,
Γ
, δ, I, F
), where
Q
is a
finite set of states, Γ is a finite alphabet,
δ ⊆ Q ×
Γ
∗
×
Γ
∗
× Q
is a finite set of transition
rules,
I ⊆ Q
(resp.
F ⊆ Q
) is a finite set of initial (resp. final) states. The transducer is
letter-to-letter if δ ⊆ Q × Γ × Γ × Q.
We will write
q
ω
1
/ω
2
−−−−−→ q
0
if (
q, ω
1
, ω
2
, q
0
)
∈ δ
. Let
−→
∗
be the smallest relation such
that
q
/
−−−−→
∗
q
for every
q ∈ Q
; if
q
ω
1
/ω
2
−−−−−−→
∗
q
0
and
q
0
ω
3
/ω
4
−−−−−→ q
00
, then
q
ω
1
ω
3
/ω
2
ω
4
−−−−−−−−−→
∗
q
00
.
A FST
T
transduces a string
ω
1
∈
Γ
∗
into a string
ω
2
∈
Γ
∗
if there exist states
q
0
∈ I
and
q
f
∈ F
such that
q
0
ω
1
/ω
2
−−−−−−→
∗
q
f
. The language
L
(
T
) of a FST
T
is the set of pairs (
ω
1
, ω
2
)
such that T can transduce ω
1
into ω
2
.
A transduction
τ ⊆
Γ
∗
×
Γ
∗
is a relation over Γ
∗
. A transduction
τ
is rational (regular)
and length-preserving if there is a letter-to-letter transducer
T
such that
τ
=
L
(
T
). Let
τ
id
denote the identity transduction, i.e.,
τ
id
=
{
(
ω, ω
)
| ∀ω ∈
Γ
∗
}
. In the rest of this
paper, we assume that transductions (resp. transducers) are length-preserving rational (resp.
letter-to-letter) unless stated explicitly, and we do not differentiate the terms transduction
and transducer. Given a transduction τ, let τ(ω) = {ω
0
| (ω, ω
0
) ∈ τ } for ω ∈ Γ
∗
.
The composition ◦ of two transductions τ
1
, τ
2
is defined as
τ
1
◦ τ
2
= {(ω
1
, ω
3
) | ∃ω
2
∈ Γ
∗
, (ω
1
, ω
2
) ∈ τ
1
and (ω
2
, ω
3
) ∈ τ
2
}.
I Proposition 2. For every transduction τ, τ ◦ τ
id
= τ = τ
id
◦ τ .
The left quotient
d·, ·c
−1
over transductions is defined as follows:
∀ω
1
, ω
2
∈
Γ
∗
with
|ω
1
| = |ω
2
|, dω
1
, ω
2
c
−1
τ = {(ω, ω
0
) | (ω
1
ω, ω
2
ω
0
) ∈ τ }.
I Proposition 3. [30] For every ω
1
, ω
2
∈ Γ
n
, for every transduction τ
1
, τ
2
,
dω
1
, ω
2
c
−1
(τ
1
◦ τ
2
) =
[
ω
3
∈Γ
|ω
1
|
(dω
1
, ω
3
c
−1
τ
1
) ◦ (dω
3
, ω
2
c
−1
τ
2
)
.
Let
T
be a set of transductions, the closure
hT i
∪
of
T
over the composition
◦
, left quotient
d·, ·c
−1
and union ∪ is defined as follows:
T ⊆ hT i
∪
, ∅ ∈ hT i
∪
and τ
id
∈ hT i
∪
;
if τ
1
, τ
2
∈ hT i
∪
, then τ
1
◦ τ
2
∈ hT i
∪
and τ
1
∪ τ
2
∈ hT i
∪
;
if τ ∈ hT i
∪
, then dγ, γ
0
c
−1
τ ∈ hT i
∪
for all γ, γ
0
∈ Γ.
Similarly, let
hT i
denote the closure of
T
over the composition
◦
and left quotient
d·, ·c
−1
.
I Proposition 4. (a) The set hT i is finite iff the set hT i
∪
is finite.
(b) The set
hT i
∪
is the semigroup generated by (
hT i, ∪
), that is,
∀τ ∈ hT i
∪
,
∃τ
1
, ..., τ
m
∈
hT i for m ≥ 1 such that τ =
S
m
i=1
τ
i
.
2.2 Pushdown Systems with Transductions
Pushdown systems with transductions (TrPDSs) [
30
] are an extension of pushdown systems
by associating each transition with a transduction which modifies the stack content by
applying the transduction. This extension allows TrPDSs to model sequential programs that
manipulate the stack content rather than only the top of the stack.
C O N C U R ’ 1 5
剩余14页未读，继续阅读
weixin_38626943
- 粉丝: 5
- 资源: 935
我的内容管理
展开
最新资源
- 解决Eclipse配置与导入Java工程常见问题
- 真空发生器：工作原理与抽吸性能分析
- 爱立信RBS6201开站流程详解
- 电脑开机声音解析：故障诊断指南
- JAVA实现贪吃蛇游戏
- 模糊神经网络实现与自学习能力探索
- PID型模糊神经网络控制器设计与学习算法
- 模糊神经网络在自适应PID控制器中的应用
- C++实现的学生成绩管理系统设计
- 802.1D STP 实现与优化：二层交换机中的生成树协议
- 解决Windows无法完成SD卡格式化的九种方法
- 软件测试方法：Beta与Alpha测试详解
- 软件测试周期详解：从需求分析到维护测试
- CMMI模型详解：软件企业能力提升的关键
- 移动Web开发框架选择：jQueryMobile、jQTouch、SenchaTouch对比
- Java程序设计试题与复习指南
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
