运行DFA 扩充后的映射M的定义: MR,E)=R表示一定要有输入符号后, DFA的状态才可能改变。 M(RTt=M(M(R,T))表示状态的改变是 从左到右进行的。 定义:字符串t被DFA接受当且仅当M(S,t 在F中
运行DFA • 扩充后的映射M的定义： – M(R, ) = R 表示一定要有输入符号后， DFA的状态才可能改变。 – M(R,Tt)=M(M(R,T),t) 表示状态的改变是 从左到右进行的。 • 定义：字符串t被DFA接受当且仅当M(S,t) 在F中
DFA接受的符号串集合 定义:(①DA所能够接受的所有字符串的 集合写成LD),L①D是正则集合, 定理33设G为正则文法,如果x数据L(G), 那么它能被G相应的有穷自动机所接受 定理34接受正则语言L的最小状态自动 机不记同构是唯一的
DFA接受的符号串集合 • 定义：(D)FA所能够接受的所有字符串的 集合写成L(D)，L(D)是正则集合，。 • 定理3.3 设G为正则文法，如果x数据L(G)， 那么它能被G相应的有穷自动机所接受。 • 定理3.4 接受正则语言L的最小状态自动 机不记同构是唯一的
非确定有穷状态自动机NFA 在前面的从正则文法构造FA的例子中, 恰好从一个状态射出的弧的标记是两两 不同的。但是,如果有两个规则V:=UT 和W:=UT,那么从U到Ⅴ和W的弧的标记 都是T。 此时,不能用DFA的映射来表示状态为U 时,输入T时的后继状态。也就是说,当 状态为U,输入为T时,这个转换图的下 步动作出现了不确定性。这个状态转 换图不再是DFA
非确定有穷状态自动机NFA • 在前面的从正则文法构造FA的例子中， 恰好从一个状态射出的弧的标记是两两 不同的。但是，如果有两个规则V::=UT 和W::=UT，那么从U到V和W的弧的标记 都是T。 • 此时，不能用DFA的映射来表示状态为U 时，输入T时的后继状态。也就是说，当 状态为U，输入为T时，这个转换图的下 一步动作出现了不确定性。这个状态转 换图不再是DFA
不确定状态转换图的例子 Z: -Za Aa bb A: =Ba Za a B: =Ab Bab
不确定状态转换图的例子 • Z::= Za | Aa | Bb • A::= Ba | Za | a • B::=Ab | Ba | b S A B Z a b a b a b a a a
NFA的定义 定义:一个DFA是(K,M,S,F) 有穷非空状态集合 K∑Ms 有穷的输入字母表集合 从K×M到K的超集的映射 是K的子集,称为开始状态集合 K的子集,称为终止状态集合。 NFA和DFA的不同在于 M的值域是K的超集。 开始状态有不止一个
NFA的定义 • 定义：一个DFA是(K,,M,S,F) – K 有穷非空状态集合 – 有穷的输入字母表集合 – M 从KM到K的超集的映射。 – S 是K的子集，称为开始状态集合。 – F K的子集，称为终止状态集合。 • NFA和DFA的不同在于: – M的值域是K的超集。 – 开始状态有不止一个