1.正规式:
(a|b...|z)(a|b...|z|1|2...|9|0)* 必须由小写字母开头,组成的数字与字母的串
DFA 状态转换图
2.左线性文法画状态转换图
在左线性文法中,假设终结符为礼物,如果是A - > a,就是开始符号S送礼物a给A,而A - >Ba,可以理解为B送礼物给A,也可以理解为归约,B获得了a然后能推出A
右线性文法
左线性文法的例子:
ababaaa可以成功的从开始状态走到终止状态,正规文法可以推导出字符串ababaaa
3.五元组定义有穷自动机
D1 = (K,∑,M,S,F)
K = {S,A,B,Z} 状态的集合
∑ = {a,b} 可接受的输入字符
M : M(S,a) = A M(S,b) = B
M(B,a) = Z M(A,b) = B
M(B,a) = A M(B,b) = Z
M(Z,a) = Z
S = S 有穷自动机的初态
F = {Z} 终态的集合
4.NFA的确定化(NFA - > DFA)
简化子集法(不能出现空串)
状态转换表(矩形表式)
K\∑ | 0 | 1 |
S | V,Q | Q,U |
V | Z | |
Q | V | Q,U |
U | Z | |
Z | Z | Z |
构造等价的DFA(K',∑,M',S',F')
M' :
k'\∑ | 0 | 1 |
[S] | [V,Q] | [Q,U] |
[V,Q] | [Z,V] | [Q,U] |
[Q,U] | [V] | [Q,U,Z] |
[Z,V] | [Z] | [Z] |
[V] | [Z] | |
[Q,U,Z] | [V,Z] | [Q,U,Z] |
[Z] | [Z] | [Z] |
S' = [S] F' = { [V,Z] , [Q,U,Z] , [Z] }