已阅读5页,还剩8页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
常见题型题目给定一正规式 要求给出其NFA DFA或最简DFA形式 题目给定一用状态图表示的NFA 要求给出其对应的DFA或最简DFA形式 题目给定一NFA DFA或最简DFA 要求给出其对应的正规式 题目给定一正规集 要求给出其相应的DFA 题目给定一用自然语言描述的正规集 要求给出其相应的正规式或有限自动机 例题与习题解答 例4 1 写能被5整除的十进制整数的文法及正则表达式 解 能被5整除的文法 G Z Z A 0 5 A 0 1 2 3 4 5 6 7 8 9 AA如果要求 除零以外不以0开头 则文法为 G Z Z A 0 5 A AB CB 0 C BBC 0 1 2 3 4 5 6 7 8 9正则表达式 G Z Z A 0 5 A 0 1 2 3 4 5 6 7 8 9 例4 2 写一个文法 使其语言是奇数集 且每个奇数不以0开头 解 文法G N N AB BA AC DB 1 3 5 7 9D B 2 4 6 8C 0 D 例4 3 写出能被3整除十进制整数的文法和正则表达式 解 能被3整除的文法 G 0 1 2 3 4 5 6 7 8 9 S A B S P 其中P为 S 0 3 6 9 S S 1 4 7 A 2 5 8 BA 0 3 6 9 A 1 4 7 B 2 5 8 SB 0 3 6 9 B 2 5 8 A 1 4 7 S正则表达式 Z a bc cb a cibi ciabi i 1 a 0 3 6 9 b 1 4 7 c 2 5 8 例4 4 已知有限自动机如图 1 以上状态转换图表示的语言有什么特征 2 写出其正规式与正规文法 3 构造识别该语言的有限自动机DFA 解 1 L W W 0 1 并且W至少有两个连续的1 2 正则式为 0 1 11 0 1 正则文法G Z 为 A 0A 1A 1BB 1C 1C 0C 1C 0 1 3 将图中有限自动机确定化 首先从处态A出发 II0I1 1 A 1 A 2 A B 2 A B 1 A 3 A B C 3 A B C 4 A C 3 A B C 4 A C 4 A C 3 A B C 其相应的DFA如下图 将这个DFA最小化 首先分终态和非终态两个集K1 1 2 和K2 3 4 由于状态1输入1到达状态K1集 而状态2输入1到达K2集故将k1分为K11 1 K12 2 由于状态3 和4输入1 或0都到达k2集所以状态3 4等价 则可以分割成三个子集 1 2 3 4 所以将DFA最小化的状态图如下 解 1 首先构造NFA 2 由系统转换图构造DFA NFA确定化 设初态为 S A B G F 例4 5 请构造与正则式R a b ba a b 等价的状态最少的DFA 确定有限自动机 NFA确定化为DFA的过程 IIaIb 1 S A B G F 2 G F 3 A B C G F 2 G F 2 G F 4 A B G F 3 A B C G F 5 D F G E Z 3 A B C G F 4 A B G F 2 G F 3 A B C G F 5 D F G E Z 6 G F E Z 7 A B E Z G F 6 G F E Z 6 G F E Z 7 A B E Z G F 7 A B E Z G F 6 G F E Z 8 A B C E Z G F 8 A B C E Z G F 5 D F G E Z 8 A B C E Z G F DFA这状态图如下 确定有限自动机图如下 3 将DFA最小化 先将终态和非终态分成两个集 K1 1 2 3 4 K2 5 6 7 8 对于K1中的3态输入a则进入K2集 而1 2 4态输入a仍然在K1中 故K1可一分为二K11 1 2 4 和K12 3 考察K11对于1 4态输入b到达3态而2态输入b到
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 应急管理行政案件简案快办程序规定
- 临床心功能不全护理评估、护理诊断及健康教育
- 《食品安全》课件-淀粉的糊化
- 扫路车项目综合评估报告
- 现代农业技术:火龙果病虫害课件
- 河北科冠通达液压制造有限公司年产1.2万条液压油缸喷漆件技术改造项目环评报告
- 衡水荣瑞金属橡塑有限公司尼龙塑料、焊接件成型加工扩建项目环评报告
- 疫情数据实时监测技术方案
- 住房保障政策与房地产供给
- 职业性传染病:美发师健康须知
- V型滤池设计计算书2021
- 骨科专科科普知识讲座
- 桶装水营销方案
- 《机械识图》考试试卷及答案
- 数学与控制理论的结合:探索数学在自动化控制中的应用
- 餐券模板完整
- 大学生跨文化交际能力的现状调查和对策研究
- X射线荧光光谱理论考试考试题库(选择题)
- 信息检索与利用智慧树知到课后章节答案2023年下石河子大学
- 基于项目式学习的中小学创新教育实践
- 跨文化认知与文明互鉴:埃及智慧树知到课后章节答案2023年下福州大学
评论
0/150
提交评论