第三章是常规语言.ppt

编译原理;第三章 正则语言;3.1 有穷状态自动机;3.1 有穷状态自动机;3.1 有穷状态自动机;3.1 有穷状态自动机;3.1 有穷状态自动机;FA的语法;3.1 有穷状态自动机;FA的语义( FA与语言的关系 );FA的语义( FA与语言的关系 );FA的语义( FA与语言的关系 );FA与正则语言;3.2 正则语言的封闭性;语言的性质 语言是符号串的集合 补运算 封闭性 如果语言A为正则语言，那么A的补集也是正则语言 语言封闭性的意义;证明思路;例：一个正则语言的补集;补自动机的构造;证明;在FA的计算过程中，有的时候需要“猜测”的功能 例：证明正则语言在乘积运算下封闭 普通的FA无法“猜测” 需要一种机制能够同时计算所有的可能-非确定性;NFA( Nondeterministic Finite Automata ) DFA( Deterministic Finite Automata ) NFA与DFA的区别 从DFA的每一个状态出发，对于字母表中的每一个符号，最多只有一条迁移，而NFA可以有多条。 NFA允许“空转移”，也就是能够不读入任何符号就迁移到另外的状态。;3.3 非确定性的有穷自动机;3.3 非确定性的有穷自动机;一台NFA M = ( Q, ?, ?, q0, F )，其中： Q为一个非空有穷的状态集合； ?为有穷的字母表( 符号集 )； ?：Q ? ?? → 2Q为状态迁移函数，其中??=??{?}； q0 ? Q为初始状态； F ? Q为接受状态集合。;3.3.1 NFA的形式定义;NFA的运行： M的一个运行是一个有穷的状态序列? = s0s1…sn，其中： s0 = q0； sn ? F； ?0?in( ?a???(si+1 ? ?(si, a)) )。 ;NFA接受的串： 称一个串? = a1a2…am被M接受（识别），如果存在一个串?’ = a’1a’2…a’n，其中a’1,a’2,…,a’n ???，使得?’ = ?，而且M存在一个运行? = s0s1…sn，使得： ?0?in(si+1 ? ?(si, a’i+1))。 如果串?不被M接受，则称M拒绝? 。 例： 0111可以写为01?11 ;NFA M的语言L(M)为所有M接受的串的集合。;定义：如果两台自动机识别相同的语言，则称这两台自动机等价。 定理：对于任意一台NFA，都存在等价的DFA。 证明思路：对任意的NFA，构造一台DFA，模拟NFA的运行，用DFA的一个状态去记录所有分支的状态。;3.3.3 NFA与DFA的等价性;证明：首先不考虑空转移的情况 令NFA N = ( Q, ?, ?, q0, F ) 构造DFA M = ( Q’, ?, ?’, q’0, F’ )，其中 Q’ = 2Q 对所有q’ ? Q’，a??，令?’(q’,a) = ?r?q’ ?(r,a) q’0 = {q0} F’ = {q’ ? Q’ | q’包含N的一个接受状态 };考虑空转移的情况 定义函数?-Closure 对M的一个状态q’ ? Q’， ?-Closure(q’)表示从q’中的状态出发，只经过空转移能到达的所有状态的集合 改写转移函数： ?’(q’,a) = { q?Q | 存在r ? q’，使得q ? ?-Closure(?(r,a)) }。 改写起始状态 q’0 = ?-Closure(q0);子集法 构造状态集的幂集，作为DFA的状态集； 对DFA的每一个状态，构造由其出发的迁移。 造表法( On-the-fly ) 首先构造DFA的初始状态； 对于现有DFA的状态，构造由其出发的迁移，如果迁移的目标为新状态则构造一个新的状态。;例：;推论： 一个语言是正则的，当且仅当存在一台NFA识别它。 定理： 正则语言在并运算、乘积运算、闭包运算下封闭。;并运算;乘积运算;闭包运算;利用运算符来构造语言运算的表达式，从而得到复杂的语言。 如果这些运算符为正则运算，则称这样的表达式为正则表达式。 正则运算：并、乘积、闭包。;语法：归纳定义 称R为一个正则表达式，如果R为以下情况的一种： a，a?? ? ? R1 | R2，R1 ? R2，如果R1与R2都是正则表达式 R1 · R2，如果R1与R2都是正则表达式 R1*，如果R1是正则表达式;语义：归纳定义 如果R为一个正则表达式，那么R的语言L(R)可以归纳定义如下： L(a) = {a} L(?) = {?} L(?) = ? L(R1 | R2) = L(R1) ? L(R2) L(R1 · R2) = L(R1) · L(R2) L(R1* ) = L(R1)*;R1 | R2 = R2 | R1 (R1 · R2) · R3 = R1 · (R2 · R3) (R1 ? R2)