右线性语言，正则集和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 …