3.2.2古4+∩
定义3.4确定的有穷自动机(DFA)
DFA定义为：M=(Q,Z,δ,qo,F),这里Q是有穷的状态集合，∑是输
入字母表，δ:Q×∑→Q是转换函数，qo∈Q是初始状态，FSQ是接受
状态(或终止状态)集合。
口核心是转换函数。例如δ(qo,a)=q?,表示当DFA位于状态q?,当前输入符号是a,那么DFA将会装换到状态q1。
101
3.2.2有穷自动+
例3.4图3.2可以表示DFA,M=({q0,q1,q2},{0,1},δ,qo,{q1}),这
里δ可给定为：
δ(qo,0)=q?,δ(qo,1)=q1
δ(q?,0)=qo,δ(q?,1)=92
δ(q?,0)=92,δ(q?,1)=q?
●DFA的模拟运行
●输入串01
●输入串00
图3.2DFA状态转换图
102
3.2.2
定义3.5不确定的有穷自动机(NFA)
NFA定义为：M=(Q,∑,δ,qo,F),这里Q是有穷的状态集合，∑是
输入字母表，δ是转换函数，它描述了从Q×(∑U{e})到Q有限子集的映射，qo∈Q是初始状态，FCQ是接受状态(或终止状态)集合。
口例：δ(qo,a)={q?,q?},δ(qo,ε)={q?}
中一工LLN
103
图3.3NFA状态转换图
●模拟NFA运行
●输入aa
●输入aaaaa
aq1
aq2
95
q4
104
a
3.2.3在自然语言处理中的应用
●描述文档中出现的以.cn结尾的只包含数字和字母的电子邮箱地址
[letter|digit]+@[letter|digit]+\.cnletter→[A-Za-z]
digit→[0-9]
letterordigitletterordigit
Cn
letterordigit93q4q596
图3.4用以识别电子邮箱地址的有穷自动机示意图
qoletterordigitq?
@
q2
3.3上下文无关文法和下推自动机
●上下文无关文法(Context-FreeGrammar,CFG)
●比正则文法具有更强的表达能力
●更适合描述程序设计语言和自然语言
●基于CFG,可以构造高效的语法分析技术解析语言构造
定义3.6上下文无关文法
如果文法G=(V,T,S,P)中的所有产生式具有形式
A→x,
其中A∈V且x∈(VUT)*,那么文法G是上下文无关文法。
定义3.7上下文无关语言
如果G=(V,T,S,P)是上下文无关文法，那么集合
L(G)={w∈T*:S今w}是由G生成的上下文无关语言。
106
3.3.1上下文天关文法htext-FreeGrammar,CFG)
■比正则文法具有更强的表达能力
■语言L={ab,n≥0},无法用正则文法或者正则表达式描述，但是可由上下文无关文法G:{S},{a,b},S,P描述。其中P包含产生式
S→aSb,
S→E.
生成，对于句子aabb,存在推导序列
S→aSb→aaSbb→aabb
■aabb可以从开始符号S推导得到，说明串aabb是该文法对应的语言中的句子。
■从开始符号推导得到的中间结果称为句型，全部由终结符号构成的巨型称为句子。
107
3.3.1上下文无关文法
●推导的顺序例3.5考虑文法G具有产生式
●最左推导S→aAB,
●最右推导
A→bBb,
B→A|e.
那么,推导语句abbbb的过程
S→aAB→abBbB→abAbB→abbBbbB→abbbbB→abbbb
就是一个最左推导，而
S→aAB→aA→abBb→abAb→abbBbb→abbbb
则是一个最右推导。
108
3.3.1上下文无关文法
●推导树