13-第六章_2 自动机.doc_第1页
13-第六章_2 自动机.doc_第2页
13-第六章_2 自动机.doc_第3页
13-第六章_2 自动机.doc_第4页
13-第六章_2 自动机.doc_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

2 句法结构的识别 本节要解决的问题是如何判定给定的句子是否符合文法的问题，即：句子的过程叫句法模式识别。 主要有两种识别方法，一种是通过句法分析来识别，另一种是用自动机理论来识别。 一. 有限自动机（规则文法）其中为有限状态集； 为输入字符集；有限状态集Q只读头为状态变换规则，它是由到的影射；为起始状态；为终止状态集。 例：为了识别正则语言，构造有限自动机。解：，其状态转移图如下所示： 若输入为，有： 分析完毕后，最后状态为,可被自动机识别。 若输入为，有： ，同理，可被自动机识别。 若输入为，有： 不在终止状态中，拒绝该句子。 若输入为，有： ，可被自动机识别。 若输入为，有： ，拒绝该句子。【定理】若一个语言是正规的，则这个语言一定能被一个有限自动机所识别，反过来，有一个有限自动机，则必可找到与之对应的正规文法。 有正规文法，必有有限自动机与之对应。其中： 若共个非终止符，则共个状态，多了一个终止状态，有。 ，终止符集相同。 若有，在中有。 若有，在中有。 可能有出错状态在中有(trap)。 例：心电图波形：1. 不确定的有限自动机 从一个状态出发，接受同一个输入字符，可转移到两个或更多的状态： 2. 对有限自动机而言，一个不确定的有限自动机一定存在一个确定的有限自动机与之对应。 不确定的有限自动机确定的有限自动机 个状态 个状态例：不确定的有限自动机 有状态： 确定的有限自动机 有状态： 原来： 现在： 3. 有限自动机的最小化 【定理】对于任何确定的有限自动机，有一个等价的确定的有限自动机，它的状态比其它任何等价的自动机少，若不计同构（状态重命名），这个最少状态的自动机是唯一的。（1） 去掉所有多余状态（不可到达的状态）（2） 合并所有等价的状态，等价状态的要求： 同在中或同不在中； 对任意输入的字符，转移到的新状态同在中或同不在中。 例： 的等价，记为：,化简为： 二、下推自动机（上下文无关文法） 下推自动机与上下文无关文法相对应，在自动机构成中加了一个存储器，称为下推表。有限状态集Q只读头下推表读，写头堆栈下推自动机是一个七元组： 的含义同有限自动机，为下推表的字符集，为下推表的初始内容，为状态变换规则：例：上下文无关文法，其中： ， 生成的语言为。 其几何含义为： 解：其对应的下推自动机为： ， 若输入为：输 入状 态 转 换 规 则下推表内容初始情况 分析完句子后，下推表正好为空，故自动机接受该句子。 事实上，上下文无关文法和下推自动机之间有一定的互推关系，若把上例文法化为标准型，生成规则为： 相应的状态转换规则：生成式状 态 转 换 式 用这个下推自动机识别句子的过程为： 输 入状 态 转 换 规 则下推表内容 【定理】有一个上下文无关文法，一定能找到一个不确定的下推自动机（不一
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论