13-第六章_2自动机

1§2句法结构的识别本节要解决的问题是如何判定给定的句子x是否符合文法G的问题，即：句子12?xLGorLG的过程叫句法模式识别。主要有两种识别方法，一种是通过句法分析来识别，另一种是用自动机理论来识别。TurringMachineLinear-BoundedAutomationPushDownAutomationFiniteAutomation无限制文法：图灵机上下文有关文法：线性有界自动机上下文无关文法：下推自动机正规文法：有限自动机一.有限自动机（规则文法）0,,,,fRQqF其中Q为有限状态集；为输入字符集；为状态变换规则，它是由Q到Q的影射；0q为起始状态；F为终止状态集。|,qfLRxxxF0从开始扫描输入后停在中的某个状态,,,,,......abcabx有限状态集Q只读头2例：为了识别正则语言|,0nLGxxabn，构造有限自动机0,,,,fRQqF。解：01,Qqq，,ab，1Fq000111:,,,,,,qaqqbqqaqb其状态转移图如下所示：q0q1最终状态a入口b①若输入为aaab，有：00001aaabqqqqq分析完毕后，最后状态为1qF,可被自动机识别。②若输入为aab，有：0001aabqqqq，同理，可被自动机识别。③若输入为aa，有：000aaqqq不在终止状态中，拒绝该句子。④若输入为b，有：01bqq，可被自动机识别。⑤若输入为bba，有：01bbqq，拒绝该句子。【定理】若一个语言是正规的，则这个语言一定能被一个有限自动机所识别，反过来，有一个有限自动机，则必可找到与之对应的正规文法。有正规文法0,,,NTGVVPX，必有有限自动机0,,,,fRQqF与之对应。其中：3①若01,,......NnVXXX共1n个非终止符，则011,,......,nnQqqqq共2n个状态，多了一个终止状态1nq，有1nFq。②TV，终止符集相同。③若有:ijPXaX，在中有,ijqaq。④若有:iPXa，在中有1,inqaq。⑤可能有出错状态在中有Tq(trap)。例：心电图波形：qCqEqDqBqAqTppbbbtbrp.r.tr.tr.tp.r.tp.b.tb.r.tpp.r.b正常：prbtbbbqHq01.不确定的有限自动机从一个状态出发，接受同一个输入字符，可转移到两个或更多的状态：q0aaq12.对有限自动机而言，一个不确定的有限自动机一定存在一个确定的有4限自动机与之对应。不确定的有限自动机确定的有限自动机k个状态2k个状态例：不确定的有限自动机3k有状态：012,,qqq确定的有限自动机28k有状态：012010102021212012012,,,,,,,,,,,,qqqqqqqqqqqqqqqq原来：002,,qaqq21,qaq现在：002,qaq0202021012012,,,,,,qaqaqaqqqqqqq3.有限自动机的最小化【定理】对于任何确定的有限自动机fR，有一个等价的确定的有限自动机minfR，它的状态比其它任何等价的自动机少，若不计同构（状态重命名），这个最少状态的自动机是唯一的。（1）去掉所有多余状态（不可到达的状态）（2）合并所有等价的状态,ijqq，等价状态的要求：①,ijqq同在F中或同不在F中；②对任意输入的字符a，转移到的新状态,,,ijqaqa同在F中或同不在F中。5例：q0qA11000011001011qEqBqCqDqFq0qAqBqCqDqFqEADCB01BCFE,,,,BCDEFqqqqq的等价，记为：BCDEFq,化简为：qBCDEFq0qA01010,16二、下推自动机（上下文无关文法）下推自动机与上下文无关文法相对应，在自动机构成中加了一个存储器，称为下推表。下推自动机是一个七元组：00,,,,,,pRQqZF0,,,QqF的含义同有限自动机，为下推表的字符集，0Z为下推表的初始内容，为状态变换规则：*QQ例：上下文无关文法,,,,,,,GSAabcdPS，其中：:PScA，AaAb，Ad生成的语言为|,0nnLGxxcadbn。其几何含义为：…………bbbaaadc解：其对应的下推自动机为：00,,,,,,,,,,,,,pRqabcdSABCDqS000:,,,,,qcSqDABqC,,,,,......abcabx有限状态集Q只读头下推表读，写头堆栈700,,,qaDq000,,,,,qaAqABqCB00,,,qdCq，00,,,qbBq若输入为xcaadbb：输入状态转换规则下推表内容初始情况Sc00,,,qcSqDABDABa00,,,qaDqABa00,,,qaAqCBCBBd00,,,qdCqBBb00,,,qbBqBb00,,,qbBq分析完句子后，下推表正好为空，故自动机接受该句子。事实上，上下文无关文法和下推自动机之间有一定的互推关系，若把上例文法化为G标准型，生成规则为：ScAAaABAdBb相应的状态转换规则：生成式状态转换式ScA00,,,qcSqAAaAB00,,,qaAqABAd00,,,qdAqBb00,,,qbBq8用这个下推自动机识别句子caadbb的过程为：输入状态转换规则下推表内容Sc00,,,qcSqAAa00,,,qaAqABABa00,,,qaAqABABBd00,,,qdAqBBb00,,,qbBqBb00,,,qbBq①【定理】有一个上下文无关文法G，一定能找到一个不确定的下推自动机（不一定唯一），它识别的语言()pLR正好为LG，反过来也成立。②不能说，有一个不确定的下推自动机，一定能找到一个确定的下推自动机与之对应。