T
1
T
2
FST 的每一个转移用两个符号标记，一个指明该转移的输入符号，另一个指明输出符号。两个符号之间
用斜杠“/”把它们分开。在 T
1
中，从 q
1
到 q
2
的转移有输入符号 2 和输出符号 1。某些转移可能有多对输入-
输出，比如 T
1
中从 q
1
到它自身的转移。FST 在对输入串 w 计算时，从起始状态开始，一个接一个地取输
入符号 w
1
w
n
，并且比照输入标记和符号序列 w
1
w
n
=w 进行转移。每一次沿一个转移走一步，输出对
应的输出符号。例如，对输入 2212011，机器 T
1
依次进入状态 q
1
, q
2
, q
2
, q
2
, q
2
, q
1
, q
1
, q
1
和输出 1111000。对
输入 abbb，T
2
输出 1001。给出在下述每一小题中机器进入的状态序列和产生的输出。
a. T
1
对输入串 011, 输出：000, 状态序列：q
1
, q
1
, q
1
, q
1
.
b. T
1
对输入串 211, 输出：111, 状态序列：q
1
, q
2
, q
2
, q
2
.
c. T
1
对输入串 0202, 输出：0101, 状态序列：q
1
, q
1
, q
2
, q
1
, q
2
。
d. T
2
对输入串 b, 输出：1, 状态序列：q
1
, q
3
.
e. T
2
对输入串 bbab, 输出：1111, 状态序列：q
1
, q
3
, q
2
, q
3
, q
2
.
f. T
2
对输入串 bbbbbb, 输出：110110, 状态序列：q
1
, q
3
, q
2
, q
1
, q
3
, q
2
, q
1
。
g. T
2
对输入串, 输出：, 状态序列：q
1
。
1.25 给出有穷状态转换器的形式定义。
解：有穷状态转换器 FST 是一个五元组(Q,Σ,Г,δ,q0)
1) Q 是一个由穷集合，叫做状态集
2) Σ 是一个由穷集合，叫做输入字母表
3) Г 是一个由穷集合，叫做输出字母表
4) δ：Q×ΣQ×Г 是转移函数
5) q
0
是起始状态
FST 计算的形式定义：
M=(Q,Σ,Г,δ,q
0
)是一台由穷状态转换器，w=w
1
w
2
w
n
是输入字母表上的一个字符串。若存在 Q 中的状
态序列：r
0
, r
1
, r
n
和输出字母表上的一个字符串 s=s
1
…s
n
, 满足下述条件：
1）r
0
=q
0
;
2） δ(r
i
,w
i+1
)=(r
i+1
, s
i+1
), i=0,1,,n-1
则 M 在 W 的输入下输出 s.
1.26 利用你给练习 2.20 的答案，给出练习 2.19 中画出的机器 T
1
和 T
2
的形式描述。
解：有穷状态转换器 T
1
的形式描述为：
T
1
=({q
1
, q
2
}, {0，1，2},δ, q
1
, {0,1})
其中转移函数为：
0 1 2
q
1
q
1
/0 q
1
/0 q
2
/1
q
2
q
1
/0 q
2
/1 q
2
/1
- 8 -
剩余43页未读，继续阅读
Vermillion-
- 粉丝: 6
- 资源: 2
我的内容管理
展开
最新资源
- Lombok 快速入门与注解详解
- SpringSecurity实战：声明式安全控制框架解析
- XML基础教程：从数据传输到存储解析
- Matlab实现图像空间平移与镜像变换示例
- Python流程控制与运算符详解
- Python基础：类型转换与循环语句
- 辰科CD-6024-4控制器说明书：LED亮度调节与触发功能解析
- AE particular插件全面解析：英汉对照与关键参数
- Shell脚本实践：创建tar包、字符串累加与简易运算器
- TMS320F28335：浮点处理器与ADC详解
- 互联网基础与结构解析：从ARPANET到多层次ISP
- Redhat系统中构建与Windows共享的Samba服务器实战
- microPython编程指南：从入门到实践
- 数据结构实验：顺序构建并遍历链表
- NVIDIA TX2系统安装与恢复指南
- C语言实现贪吃蛇游戏基础代码
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
