故 xyyz 不是 A
2
的成员。违反泵引理的条件 1，矛盾。
∴A
2
不是正则的。
c. A
3
={a
2
n
| n�0}.(在这里，a
2
n
表示一串 2
n
个 a .)
证明：假设 A
3
是正则的。设 p 是泵引理给出的关于 A
3
的泵长度。
令 S= a
2
p
，
∵S 是 A
2
的一个成员且 S 的长度大于 p，所以泵引理保证 S 可被分成 3 段 S=xyz 且满足泵引理
的 3 个条件。即对任意的 i�0，xy
i
z 都应在 A
3
中，且 xy
i
z 与 xy
i+1
z 的长度都应是 2 的幂. 而且 xy
i+1
z
的长度应 是 xy
i
z 的长 度的 2
n
倍(n�1) 。于 是可 以选 择足 够大 的 i， 使得 |xy
i
z|=2
n
>p. 但是
|xy
i+1
z|-|xy
i
z|=|y|�p. 即|xy
i+1
z|<2
n+1
, 矛盾。
∴A
3
不是正则的。
1.30 下面“证明”0
*
1
*
不是正则语言，指出这个“证明”中的错误。(因为 0
*
1
*
是正则的，所以一定错
误。) 采用反证法证明。假设 0
*
1
*
是正则的。令 P 是泵引定理给出的关于 0
*
1
*
的泵长度。取 S 为字符
串 0
p
1
p
。S 是 0
*
1
*
的一个成员，但是例 2.38 已证明 S 不能被抽取。于是得到矛盾，所以 0
*
1
*
不是正则
的。
解：在例 2.38 中的语言是{0
n
1
n
| n�0}，取 S 为字符串 0
p
1
p
，S 确实不能被抽取；但针对语言
0
*
1
*
，S 是能被抽取的。将 S 分成三段 S=xyz，由泵引理的条件 3，y 仅包含 0，而 xy
i
z 属于语
言 0
*
1
*
，即 S 能被抽取，故题设中的“证明”不正确。
1.24 有穷状态转换器(FST)是确定性有穷自动机的一种类型。它的输出是一个字符串，而不仅仅是接
受或拒绝。图 2—39 是两台有穷状态状态转换器 T
1
和 T
2
的状态图。
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×Г是转移函数
2/1
0/0
1/0
0/0
q
1
q
2
1/1
2/1
b/1
a/0
q
3
q
2
q
1
b/0
a/1
b/1
a/1
剩余36页未读，继续阅读
尹子先生
- 粉丝: 23
- 资源: 324
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- 谷歌文件系统下的实用网络编码技术在分布式存储中的应用
- 跨国媒体对南亚农村社会的影响：以斯里兰卡案例的社会学分析
- RFM2g接口驱动操作手册：API与命令行指南
- 基于裸手的大数据自然人机交互关键算法研究
- ABAQUS下无人机机翼有限元分析与局部设计研究
- TCL基础教程：语法、变量与操作详解
- FPGA与数字前端面试题集锦：流程、设计与Verilog应用
- 2022全球互联网技术人才前瞻：元宇宙驱动下的创新与挑战
- 碳排放权交易实战手册（第二版）：设计与实施指南
- 2022新经济新职业洞察：科技驱动下的百景变革
- 红外与可见光人脸融合识别技术探究
- NXP88W8977：2.4/5 GHz 双频 Wi-Fi4 + Bluetooth 5.2 合体芯片
- NXP88W8987：集成2.4/5GHz Wi-Fi 5与蓝牙5.2的单芯片解决方案
- TPA3116D2DADR: 单声道数字放大器驱动高达50W功率
- TPA3255-Q1：315W车载A/D类音频放大器，高保真、宽频设计
- 42V 输入 5A 降压稳压器 TPS54540B-Q1 的特点和应用
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
