第三章 有穷自动机.ppt

第三章有穷自动机 本章介绍有关有穷自动机的基本概念和理论以及正规文法 正规表达式与有穷自动机之间的相互关系 3 1有穷自动机的形式定义 有穷状态自动机 Finite stateAutomata或简称FA 在识别功能上与正规文法类等价 而且也等价于一个特殊类型的语言产生器 正规表达式 RegularExpression 因此许多简单的程序语言都可由FA所识别 事实上 它是描述词法的有效工具 也是进行词法分析的主要理论基础 有穷自动机分为两类 1 确定的有穷自动机 DeterministicFiniteAutomata简称DFA 2 不确定的有穷自动机 NondeterministicFiniteAutomata简称NFA 3 1 1确定有穷自动机的形式定义一个DFAM K f S Z 其中 K是一个有限状态集合 是一个字母表 它的每个元素称为一个输入字符 S K S称为初始状态 唯一 Z K Z称为终态集合 终态也称可接受状态或结束状态 f是转换函数 是一个从K 到K的单值映射 f ki a kj ki kj K a kj称为ki的一个后继状态 确定性的体现 初始状态唯一 转换函数为单值映射 例 设DFAM S U V Q a b f S Q 其中f S a U f S b Vf U a Q f U b Vf V a U f V b Qf Q a Q f Q b Q因为 1 初始状态唯一是S 2 每个转换函数均为单值映射 所以该FA为确定有穷自动机 3 1 2状态转换表DFA的映射关系可以由一个矩阵表示 矩阵的行标表示状态 列标表示输入字符 矩阵元素表示f s a 的值 这个矩阵称为状态转换表 f S a Uf S b Vf U a Qf U b Vf V a Uf V b Qf Q a Qf Q b Q 3 1 3状态转换图图中标有 的为开始状态 标有双圈的状态为终止状态 若f Ki a Kj 则从状态结点Ki到状态Kj画标记为a的弧 3 1 4自动机的等价性为了讨论自动机的等价性 先对DFA中的映射进行扩充 扩充的转换函数f设Q K 函数f Q Q 即如果输入字符是空串 则仍停留在原来的状态上 对 Q K T t1 f Q Tt1 f f Q T t1 该定义是一个递归定义 说明当自动机处在状态Q且面临某个输入串Tt1时 则先应用函数f Q T P 然后应用函数f P t1 DFA的确定性表现在转换函数f K K是一个单值函数 即对任何状态k K和输入符号a f k a 唯一地确定了下一个状态 从状态转换图来看 若字母表 含有n个输入字符 那么任何一个状态结点最多有n条弧射出 且每条弧以一个不同的输入字符标记 自动机接受字符串x如果对于某一自动机M K f S Z x 有f S x P 且P Z 则x为该自动机M所接受 识别 即自动机从开始状态开始 在读完全部输入串以后 自动机恰恰到达终止状态 则该输入串能被该自动机所接受 例 DFAM S A B C 0 1 S S 且 定义为 S 0 B S 1 A A 0 C A 1 S B 0 S B 1 C C 0 A C 1 B状态图表示 矩阵表示 自动机处理字符串110101和11101的轨迹 S 110101 S 1 10101 A 10101 A 1 0101 S 0101 S 0 101 B 101 B 1 01 C 01 C 0 1 A 1 S 接受 S 11101 S 1 1101 A 1101 A 1 101 S 101 S 1 01 A 01 A 0 1 C 1 B 拒绝 所有为自动机M所能接受的串组成一个集合 称这个集合为自动机M所能接受的语言 用L M 表示 L M t f S t Z t 对于任何两个有穷自动机M和M 如果L M L M 则称M与M 是等价的 3 1 5非确定有穷自动机NFA定义一个不确定的有穷自动机NFAM 是一个五元组 M K f S Z 一个含有m个状态和n个输入字符的NFA可表示为一张状态转换图 该图含有m个状态结 每个结可射出若干条箭弧与别的结点相连接 每条弧用 中的一个字 不一定要不同的字 且可以为空字 作标记 称输入字 整个图至少含有一个初态结以及若干个终态结 NFA与DFA的区别NFA有一个开始状态集 而DFA只有一个开始状态 NFA的映射是Q Q的子集 是一个多值映射 而DFA的映射是Q Q 是一个单值映射 DFA是NFA的特例 对于每个NFAM 存在一个DFAM 使得L M L M 对于 中的任何一个串t 如果存在一条从某一初态结到某一终态结的道路 且这条道路上的所有弧的标记依序连接成的串等于t 则称t可为NFAM所识别 读出或接受 若M的某些结既是初态结 又是终态结 或者存在一条从某个初态结到某个终态结的 道路 则空字可为M所接受 例 NFAM 0 1 2 3 4 a b f 0 2 4 f 0 a 0 3 f 2 b 2 f 0 b 0 1 f 3 a 4 f 1 b 2 f 4 a 4 f 2 a 2 f 4 b 4 可用状态图或矩阵表示 3 2 1确定化 造表法造表法是一种简单而有效的确定化方法 定义 设NFAM Q t Q0 F 假定I是M中状态集的一个子集 定义 closure I 如下 若q I 则q closure I 若q closure I q 是由q出发经多条 弧到达的状态 则q closure I 3 2NFA到DFA的转换 定义 假定I是NFAM中状态集的一个子集 a 定义Ia closure J 其中J是所有那些可从子集I中的任一状态出发 经过一条a连线 跳过a连线前的 连线 而到达的状态 结 的全体 造表法的具体步骤 假定给定的NFAM中 仅含两个符号a b 可用如下方法将M确定化 采用造表的方式 该表的每一行有三列 若 中含有n个符号 则该表有n 1列 第一列记为I 第二 三列分别记为Ia Ib 置该表的第一行第一列为 closure Q0 即一列包含M初态集Q0的 闭包 然后计算它的Ia和Ib 分别填入第二 三列上 一般 若某一行的第一列上的I已确定 便可根据前述定义求出这一行的第二 第三列上的Ia和Ib 检查Ia和Ib 看它们是否已在表的第一列中出现 把未曾出现者之一填入下一空行的第一列上 再计算该行的第二 第三列上的Ia和Ib 重复第二步 直至表中所有第二 第三列上的元素全部再第一列出现为止 因为M中的状态 子集 的个数是有限的 所以上述三步必定在有限步骤内终止 将由上述过程得到的最终形式的表看作一个状态转换表 即把其中第一列中的元素作为状态 把Ia Ib分别看作是输入符号a b 把其余信息看作是状态转换函数之值 这个表唯一地刻画了一个确定的有穷状态自动机M 其初态是该表第一行第一列的元素 其终态是该表中所有那些含有原终态的元素 可以证明 这个DFAM 和NFAM是等价的 例 有一NFAM 用造表法使其确定化 3 2 2确定的有穷自动机的化简所谓一个确定的有穷自动机M的化简是指 寻找一个状态数比M少的DFAM 使得L M L M 可通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机 消除多余状态多余状态是指从该自动机的开始状态出发 任何输入串也不能到达的状态 A B C 3 2 3合并等价状态等价状态若s和t是M的两个不同状态 称s和t等价 如果从状态s出发能读出某个字 而停于终态 同样从t出发也能读出同一个字 而停于终态 反之若从t出发能读出某个字 而停于终态 则从s出发也能读出同一个字 而停于终态 如果DFAM的两个状态s和t不等价 则称这两个状态是可区别的 DFA中 状态s和t等价的条件是 一致性条件 状态s和t必须同时为可接受状态 终态 或不可接受状态 非终态 蔓延性条件 对于所有输入符号 状态s和t必须转换到等价的状态里 分割法合并等价状态一个DFAM的状态化简过程就是把M的状态集划分成一些不相交的子集 使得任何不同的两子集的状态都是可区分的 而同一子集的任何两个状态都是等价的 最后 从每个子集选出一个代表 代表该子集 同时消去其它等价状态 对M的状态集S进行划分的步骤 把S的终态与非终态分开 分成两个子集 形成基本划分 属于这两个不同子集的状态是可区别的 假定某个时候 已含m个子集 记 I 1 I 2 I m 且属于不同子集的状态是可区别的 再检查 中的每个I能否进一步划分 对于某个I i 令I i S1 S2 Sk 若存在一个输入字符使得move I i a 不包含在现行 的某一子集I i 中 则将I i 一分为二 例 将图示的DFAM最小化 1 将M状态分为两个子集 P0 1 2 3 4 5 6 7 2 1 2 3 4 读入a后划为 P1 1 2 3 4 5 6 7 3 进一步划分 P2 1 2 3 4 5 6 7 4 考察 5 6 7 将P2划分为 P3 1 2 3 4 5 6 7 P3不可再划分 从而1与2 6与7等价 3 2 4从化简后的DFA到程序表示识别标识符的DFA 见图 a 需改为图 b 所示状态 其中 l代表字母 d代表数字 图 a 图 b 如果赋予状态q0 q1与q2一定的操作 则可得识别单词标识符的程序流程图 见下图 3 3正规文法与有穷自动机正规文法与有穷自动机FA有着特殊的关系 可以证明 对任何正规文法G 可以构造一个FA 它能而且只能识别语言L G 反过来 对任何FA 可以构造一个相应的正规文法G 它能生成由该FA所识别的语言 2 3 1从正规文法到FA设正规文法G有形如U aV a VT V VN或V 的产生式 由正规文法G可以直接构造一个有穷自动机A 简称自动机A 使L A L G 构造步骤如下 令正规文法G的终结符号集作为有穷自动机A的字母表 文法G的每一个非终结符都作为自动机A的一个状态 特别是文法G的开始符作为自动机A的开始状态 在自动机A中增加一个新状态z作为自动机的终止状态 对于文法G的形如U aV a VT或a V VN 的产生式 在自动机A中构造形如t U a V的映射 对文法G的形如U a a VT 的产生式 在自动机A中构造形如t U a z的映射 2 3 2从FA到正规文法从自动机也可直接构造其正规文法 构造步骤如下 自动机每一个状态的标记 均作为正规文法的非终结符 其中 自动机开始状态的标记将作为正规文法的开始符号 自动机的输入字母表中的所有符号 作为正规文法的终结符 对于自动机的映射t U a V 其中 U V为自动机的状态标记 a为输入符号 构造文法的一条产生式U aVU V为文法的非终结符 a为终结符 对于自动机的终止状态Z 在正规文法中增加一条产生式Z 3 4正规表达式与FA 正规式也称正规则式 正规表达式 与正规文法的功能一样 正规式也可用以描述程序设计语言的单词符号 3 4 1正规表达式的操作符连接假定有两个正规表达式e1和e2 它们分别产生语言L1和L2 于是定义正规表达式的连接操作为e1 e2 x y x L1 y L2 其中 可省略 选择可用 或 表示 定义为e1 e2 x x L1或x L2 重复用 表示 表示 中的表达式的0次到若干次的自重复连接 即e x x L1 例 正规表达式110由数字1 1 0连接在一起组成 且表示的语言为L 110 表达式0 1所表示的语言为L 0 1 表达式1 所表示的语言为L 1i i 0 1 2 例 用正则表达式表示 标识符 字母 字母 数字 实数 e 数字 数字数字 3 4 2正规表达式的定义所有正规表达式都可以由下列规则构造出来 是一个表示空集的正规表达式 是一个正规表达式 它所表示的语言仅包含一个空符号串 即 a是一个正规表达式 a VT它所表示的语言 它所表示的正规集 是单个符号a所组成 即 a 如果e1和e2是正规表达式 其表示的语言分别为L1和L2 e1 e2 是一个表示语言L1 L2的正规表达式 e1 e2 是一个表示语言L1L2的正规表达式 e1 是一个表示语言L1 的正规表达式 正规表达式中操作符的优先级顺序为 连接 例 正规表达式a b 表示的正规集是 ambn m 0 n 0 正规表达式 ab 表示的正规集是 ab m m 0 正规表达式 a b 表示的正规集是 x x a b 表达式 aa ab ba bb 表示在VT a b 上的所有偶长度的串 3 4 3正规表达式的等价性如果两个正规表达式表示相同的语言 则这两个正规表达式相等或等价 故有00 000 03 4 4正规表达式的性质r s s r或满足交换律r s t r s t或满足结合律 rs t r st 连接满足结合律r s t rs rt s t r sr tr分配律 r r r r 是连接的恒等元素 例 程序设计语言中的单词都能用正规式来定义 如 字母 数字 上的正规式e1 字母 字母 数字 表示的是所有标识符的集合正规式e dd 定义了无符号整数令 d e 则 上的正规式 d dd dd e dd 表示的是无符号数 3 4 5正规文法与正规式一个正规语言可以由正规文法定义 也可以由正规式定义 对任意一个正规文法 存在一个定义同一个语言的正规式 反之 对每个正规式 存在一个生成同一语言的正规文法 正规式转换成正规文法将 上的一个正规式转换成文法G VN VT P S 令其中的VT 确定产生式和VN的元素用如下方法 对任何正规式r 选择一个非终结符S 生成产生式S r 并将S定为G的识别符号 若x和y都是正规式 对形如A xy的产生式 重写为A xB B y两产生式 其中B是新选择的非终结符 即B VN 对已转换的文法中的形如A x y的产生式 重写为A xA A y对形如A x y的产生式重写为A x A y不断利用上述规则作变换 直到每个产生式最多含有一个VN为止 例 将R a a d 转换成相应的正规文法 令S是识别符号 首先形成S a a d 下一步 S aA A a d 重写为 A a d A A 进而转变为 S aA A aA A dA A 正规文法转换成正规式上述过程的逆过程 最后只剩下一个开始符号定义的产生式 并且该产生式的右部不含非终结符 转换规则 例 文法G S S aA S a A aA A dA A a A dS aA a A aA dA a d a d A a d A a d a d S a a d a d a a a d a d a a d 练习 有文法G S S aS S aB B bC C aC C a 3 4 6正规式和有穷自动机的等价性正规表达式与有穷自动机等价 是指若给定一正则表达式 也即相应地给定了正则集合L e 那么就可构造NFAM 并有L M L e 反之 若给定一个DFAM M接受的语言为L M 则必然存在一正则表达式e 且L e L M 正规表达式和FA是定义语言 符号串集 的两种不同形式 同一个语言 既可用FA描述 也可用正规表达式描述 3 4 7正规表达式到NFA的转换先构造一个NFAM的一个广义转换图 其中 只有S与Z两个状态 S是开始状态 Z是终止状态 弧上是正规表达式e 然后 按照下图所示的替换规则对正规表达式e逐步进行分解 直到转换图中所有的弧上都是S中的单个符号或e为止 替换成 替换成 替换成 例 有 a b 上的正规式R a b abb 构造NFAM使L M L e 练习 构造与 a b 上的正规式 a b aa bb a b 等价的自动机 3 4 8NFA到正规表达式的转换一个输入字母表为 的NFAM 可构造正规表达式e 使L e L M 具体操作如下 首先对NFAM进行拓广 在M的状态转换图中 设置一个唯一的开始状态S和唯一的终止状态Z 并允许状态转换图中弧上可以为正规表达式 然后从开始状态S到原来所有的开始状态连接 弧 再从原来所有的终止状态到Z状态也连接 弧 修改后构成了一个新的NFA 它只有一个初态结点S和一个终态结点Z 这个新的NFAM 显然和原NFAM等价 接着 利用下图所示的替换规则 逐步消去M 中属于M的所有结点和有关连线 直到状态转换图中只剩下状态S和Z为止 这个过程称为消结 在消结过程中 用相应的正规表达式标记连线 替换成 替换成 替换成 例 NFAM 0 1 2 3 4 a b f 0 2 4 状态图如下 构造正规式R使L R L M 3 5DFA在计算机中的表示 矩阵表示法设M是一个二维数组 若t qi qj qk 则令M i j k 其中i k 0 1 2 n j 1 2 m 表结构DFA的映射t Q Q在计算机中可表示成一种表结构 在这个表结构中 每一个状态对应一个表 表中包括该状态的状态名 从该状态发出的弧数 每条弧上的标记以及弧达到的状态所在表的首地址 DFA在计算机中的表结构 程序表示法我们也可以用程序来表示DFA 例 C语言的注释 其有穷自动机 State1 ifthenextcharacterris thenadvancetheinput State2 ifthenextcharacteris thenadvancetheinput State3 done false whilenotdonedowhilethenextinputcharacterisnot doadvancetheinput endwhile advancetheinput State4 whilethenextinputcharacteris doadvancetheinput endwhile ifthenextinputcharacteris thendone true endif advancetheinput endwhile accept State5 else otherprocessing endifelse otherprocessing endifState 1 Start whilestate 1 2 3or4docasestateof1 caseinputcharacterof advancetheinputstate 2 elsestate ErrororOther endcase2 caseinputcharacterof adva