电子科技大学：《有限自动机理论 Finite Automata Theory》课程教学资源（课件讲稿）第04章 正则语言（简化版）

右线性语言，正则集和FSL是等价的， 从不同的角度来对语言进行的描述： 右线性文法产生右线性语言； ·通过运算得到正则集； 有限状态自动机DFA(或NFA)接收 FSLo

l 右线性语言，正则集和FSL是等价的， 从不同的角度来对语言进行的描述： l 右线性文法产生右线性语言； l 通过运算得到正则集； l 有限状态自动机DFA(或NFA)接收 FSL

定理 &-NFA的开始状态可以仅有 一个 &-NFA的接收状态可以仅有一个

定理 -NFA的开始状态可以仅有一个 -NFA的接收状态可以仅有一个

思路 f S1 ● ●●●●●● : ● S四 f

思路 s1 f1 sm …… fn ……

改造为 f S d S ● ●●●●●● F ● Sm f

改造为 s1 sm S …… F f1 fn  …… 

推广 FA(DFA、NFA)可以仅有 一个开始状态和一个接收状态

推广 FA(DFA、NFA）可以仅有 一个开始状态和一个接收状态

定理 FSL对于联合、连接和迭代 三种运算是有效封闭的

定理 FSL对于联合、连接和迭代 三种运算是有效封闭的

分别接收语言L1和L2的FA M 41 ●●● fi M2 92 ●●●

分别接收语言L1和L2的FA … M1 q1 f1 … M2 q2 f2

联合：构造FA M 41 6 8 Jo f0 M2 42

… 联合：构造FA q0  f0 M1 q1 f1  M2 q2 f2   …

连接：构造FA M M2 41 ●●● 42 · fh

连接：构造FA f2 M1 q1 f1  M2 … q2 …

迭代：构造FA 8 M E 40 f 8

迭代: 构造FA f0 M1 q1 f1   q0   …