构造正则文法例子 例子:{(abvb2|n>=0
构造正则文法(例子) • 例子：{(ab)nb 2 | n>=0} S
转换系统 定义:转换系统是具有下列特征的状态 转换图: 只有唯一的开始状态S和唯一的终止状态Z; 没有弧进入S,也没有离开Z 可能有空弧
转换系统 • 定义：转换系统是具有下列特征的状态 转换图： – 只有唯一的开始状态S和唯一的终止状态Z； – 没有弧进入S，也没有离开Z – 可能有空弧。 S S2 I S1 Z1 Z2 Z
转换系统 定理3.2对于任何一个状态图,都存在 个相应的转换系统,它们接受同样的语 转换系统对于从正则表达式转换到状态 转换图起到了中间表示的作用
转换系统 • 定理3.2 对于任何一个状态图，都存在一 个相应的转换系统，它们接受同样的语 言。 • 转换系统对于从正则表达式转换到状态 转换图起到了中间表示的作用
DFA的定义 有穷状态自动机是对状态转换图的一种 形式化定义。 定义:一个DFA是(K,Σ,MS,F) K有穷非空状态集合 有穷的输入字母表集合 M从K×M到K的映射 是K中的一个状态,称为开始状态。 F K的子集,称为终止状态集合
DFA的定义 • 有穷状态自动机是对状态转换图的一种 形式化定义。 • 定义：一个DFA是(K,,M,S,F) – K 有穷非空状态集合 – 有穷的输入字母表集合 – M 从KM到K的映射。 – S 是K中的一个状态，称为开始状态。 – F K的子集，称为终止状态集合
DFA的例子 ({S,Z,A,B}2a,b}M,S,{Z}); A 其中 M(S, a)=A MS, b)=B S M(Aa)=Z M(a,b)=B MB, a)=A MB,b)=Z B M(Z,a)=Z
DFA的例子 • ({S,Z,A,B},{a,b},M,S,{Z})； • 其中 – M(S,a) = A M(S,b) = B – M(A,a) = Z M(A,b) = B – M(B,a) = A M(B,b) = Z – M(Z,a) = Z S A B Z a b a b a b a