有穷自动机又称有限状态机。
有限状态机是描述有限状态系统的机器。
有限状态系统:
有限状态机应用:
确定的有穷自动机(Deterministic Finite Automation, DFA)
DFA为一个五元组A:
A=(Q,Σ,δ,q0,F)
- Q:有穷状态集
- Σ:字母表(有穷输入符号集)
- δ:状态转移函数,δ:Q×Σ→Q
- q0:初始状态,q0∈Q
- F:终结状态集(接受状态集),F⊆Q
状态转移函数δ表示一个当前状态和输入符号的笛卡尔积到有穷状态集的映射:
Q×Σ→Q={(q,a)∣q∈Q∧a∈Σ}→Q
或者看成是一个输入状态和符号,输出状态的函数q′=δ(q,a)。
含义(DFA的使用方法)
- 给出一个由Σ中的字符所组成的字符串
- DFA按顺序读取此字符串
- DFA根据当前状态q∈Q和当前读取到的字符a∈Σ,根据状态转移函数δ改变状态到q′
- 重复3直到字符串尾,设此时状态变为qe
- 若qe∈F,则“接受”此字符串,否则“拒绝”此字符串
扩展状态转移函数δ^:让状态转移函数直接处理字符串
δ^:Q×Σ∗→Q
δ^(q,w)={qδ(δ^(q,x),a)w=εw=xa
含义:扩展状态转移函数δ^的输出状态是状态转移函数δ按顺序处理了一个字符串后最终输出的状态。
δ^(q,a1a2a3...an)=δ(δ^(q,a1a2a3...an−1),an)=δ(δ(δ^(q,a1a2a3...an−2),an−1),an)=......=δ(δ(...δ(δ^(q,a1),a2)...,an−1),an)=δ(δ(...δ(δ(δ^(q,ε),a1),a2)...,an−1),an)=δ(δ(...δ(δ(q,a1),a2)...,an−1),an)
性质
- 扩展转移函数可以从任意状态q开始处理字符串
- 对于任意的串,扩展转移函数能保证一定跳转到某个状态
证明:(∀q∈Q)(∀x∈Σ∗)(∀y∈Σ∗)δ^(q,xy)=δ^(δ^(q,x),y)
证:
- 当y=ε时,由定义可得
δ^(δ^(q,x),ε)=δ^(q,x)=δ^(q,xε)
- 假设y=w时成立,当y=wa时
δ^(δ^(q,x),wa)=δ(δ^(δ^(q,x),w),a)=δ(δ^(q,xw),a)=δ^(q,xwa)=δ^(q,xy)由δ^的定义由假设y=w时成立由δ^的定义由字符串连接的定义
DFA的语言
某个DFA定义为D=(Q,Σ,δ,q0,F),则D的所有接受的字符串的集合,称为DFAD的 语言:
L(D)={w∈Σ∗∣δ^(q0,w)∈F}
示例:设计一个DFA使其接受全部以01结尾的语言L(D)={w∣w以01结尾}
思路:
- 要识别以01结尾的串至少得有3个状态→q0→0q1→1q2→:
- 开始q0、识别了一个0之后到q1、识别了一个1之后到q2
- q2为接受状态,可以接受的字符串在识别完01之后就应该结束
- 如果q2之后还有输入明说明字符串没结束,需要再加几个状态转移过程
- q2→0q1:如果接受状态q2之后输入了0,我们应该期待再下一个输入为1,因此这时状态转移到q1
- q2→1q0:如果接受状态q2之后输入了1,之后应该重新输入01才有可能接受,因此这时状态应该转移到q0
- q1→0q1:如果q1之后又输入了0,我们应该期待再下一个输入为1,因此这时状态还是转移到q1
- q0→1q0:如果开始状态q0之后的输入就是1,那么应该等待0的出现,因此这时它应该等待,状态应该转移到q0
识别00101的过程:δ^(q0,00101)=q2
非确定的有穷自动机(Nondeterministic Finite Automation, NFA)
NFA为一个五元组N:
N=(Q,Σ,δ,q0,F)
- Q:有穷状态集
- Σ:字母表(有穷输入符号集)
- δ:状态转移函数,δ:Q×Σ→2Q
- q0:初始状态,q0∈Q
- F:终结状态集(接受状态集),F⊆Q
NFA和DFA的区别只在于状态转移函数的值域:2Q指Q的幂集,即2Q是Q的所有子集的集合。
2Q={S∣S⊆Q}
这意味着NFA状态转移函数的输出为一个状态集合而不是一个状态:{q′}=δ(q,a)。在每一个状态处,如果状态转移函数输出的状态集合中有多个状态,那么这个NFA每一个状态都要走到,对某个确定字符串的状态转移过程会呈现树状。
和DFA对于任意串都能保证转移到某个状态不同,NFA是可以卡住的:状态转移函数δ:Q×Σ→2Q并不是对每一个(q,a)∈Q×Σ都有输出,对于没有输出的情形,视为NFA卡住,不接受字符串。
扩展状态转移函数δ^:让状态转移函数直接处理字符串
δ^:Q×Σ∗→2Q
δ^(q,w)=⎩⎪⎪⎨⎪⎪⎧{q}p∈δ^(q,x)⋃δ(p,a)w=εw=xa
与DFA扩展转移函数的不同之处在于:
- 输出为集合
- 扩展转移函数输出的集合为转移函数输出集合的并集
NFA的语言
某个NFA定义为N=(Q,Σ,δ,q0,F),则N的所有接受的字符串的集合,称为NFAN的 语言:
L(N)={w∈Σ∗∣δ^(q0,w)∩F=∅}
示例:设计一个NFA使其接受全部以01结尾的语言L(N)={w∣w以01结尾}
思路:
- 同DFA解法,要识别以01结尾的串至少得有3个状态→q0→0q1→1q2→
- 如果在q2还有输入,说明没有到字符串结尾,直接不定义状态转移让NFA卡住
- 如果在q1输入了0,则说明没有到字符串结尾或是不可接受的字符串,直接不定义状态转移让NFA卡住
- q0→01q0:字符串长度大于2时,→q0→0q1→1q2→不管怎么样都会卡住,需要定义一个“等待”以让NFA在到结尾前不要全部卡住,使之在q0等待
识别00101的过程:δ^(q0,00101)={q0,q2}
示例:设计一个NFA使其接受全部以01开头或以01结尾的语言L(N)={w∣w以01开头}∪{w∣w以01结尾}
思路:
- 设计一个接受以01开头的字符串的NFA:
- 设计一个接受以01结尾的字符串的NFA:上题已设计
- 将这两个NFA连接起来:
DFA、NFA等价性:(∃一个NFA N=(Q,Σ,δ,q0,F))(L=L(N))⇔(∃一个DFA D=(Q,Σ,δ,q0,F))(L=L(D))
(∃一个NFA N=(Q,Σ,δ,q0,F))(L=L(N))⇒(∃一个DFA D=(Q,Σ,δ,q0,F))(L=L(D))
显然,DFA可以看作是一个状态转移函数输出的集合始终只有一个元素∣δ(p,a)∣≡1,p∈2Q的NFA。
(∃一个NFA N=(Q,Σ,δ,q0,F))(L=L(N))⇐(∃一个DFA D=(Q,Σ,δ,q0,F))(L=L(D)):子集构造法(分支状态广度优先遍历)
假定有任意NFA:
N=(QN,Σ,δN,q0,FN)
构造一个DFA:
D=(QD,Σ,δD,{q0},FD)
其中:
- QD=2QN:DFA的状态集是NFA状态集的幂集
- NFA一步可以取多个值,判断过程为树形,输入不同的值生成不同的树,DFA的状态就是由某个树的某一层的多个值所组成的集合
- NFA中的每一种可能同时存在的状态组合(树的一层)都是DFA中的一个状态(相当于DFA的状态由NFA中的状态组合而成)
- FD={S∣S⊆QN∧S∩FN=∅}:DFA的接受状态是DFA的状态集2QN中与NFA接受状态集相交的状态集合的集合
- NFA只要有一个分支输出了接受状态就接受,反映到DFA中就是结束时输出的状态集合中包含接受状态
- δD(q,a)=⋃p∈qδN(p,a):DFA的状态转移函数输出为NFA状态转移函数对树中当前层状态输入下的输出状态集所组成的并集
那么,L(D)=L(N)。
证明子集构造法的正确性
思路:要证L(D)=L(N),即证它们对于任意输入字符串,最终状态都相等(∀w∈Σ∗)(δ^D({q0},w)=δ^N(q0,w))
证明:
用数学归纳法:
- w=ε时,由DFA和NFA扩展转移函数的定义有δ^D({q0},ε)={q0}=δ^(q0,ε)成立
- 若x∈Σ∗时δ^D({q0},x)=δ^N(q0,x)成立,那么对于w=xa:
δ^N(q0,w)=δ^N(q0,xa)=p∈δ^N(q0,x)⋃δN(p,a)=p∈δ^D({q0},x)⋃δN(p,a)=δD(δ^D({q0},x),a)=δ^D({q0},xa)=δ^D({q0},w)由假设由NFA的定义由归纳假设由子集构造法的定义由DFA扩展转移函数的定义由归纳假设
因此有(∀w∈Σ∗)(δ^D({q0},w)=δ^N(q0,w)),进而:
w∈L(N)⇔δ^N(q0,w)∩FN=∅⇔δ^D({q0},w)∩FN=∅⇔δ^D({q0},w)∩FD=∅⇔w∈L(D)由NFA语言的定义由上已证由子集构造法的定义由DFA语言的定义
所以L(D)=L(N)。
证毕。
非确定性不能增加有穷自动机的能力
因为有穷自动机能记住的状态是有限的,非确定性并不能让有穷自动机记住无限的状态。(可能需要其他知识才能理解)
带有空转移的有穷自动机(ε-NFA)
ε-NFA是可以在不读入字符串就进行状态转移的NFA。
ε-NFA为一个五元组N:
N=(Q,Σ,δ,q0,F)
- Q:有穷状态集
- Σ:字母表(有穷输入符号集)
- δ:状态转移函数,δ:Q×(Σ×{ε})→2Q
- q0:初始状态,q0∈Q
- F:终结状态集(接受状态集),F⊆Q
示例:设计L={w∈{0,1}∗∣w最后三个字符至少有一个是1}
用NFA设计
方法1
- 开始接收到1就跳转到全部状态,此后每接收到一个字符就往后跳一个状态。
- 没有接收到1时永远停在q0。
- 只要跳转到除q0外的任一状态,如果三步之内字符串不结束状态就卡住,从而达到“识别最后三个字符”的目的。
方法2
- 开始接收到1就跳转到下一个状态,接收到1之后再跳转的任意状态都接受。
- 没有接收到1时永远停在q0。
- 只要跳转到除q0外的任一状态,如果三步之内字符串不结束状态就卡住,从而达到“识别最后三个字符”的目的。
用ε-NFA设计
- 开始接收到1就跳转到下一个状态。
- 只要跳转到除q0外的状态,就自动跳转到q2和q3状态。
- 没有接收到1时永远停在q0。
- 只要跳转到除q0外的任一状态,如果三步之内字符串不结束状态就卡住,从而达到“识别最后三个字符”的目的。
Next-正则表达式