有限自动机理论03章有限状态自动机

递归扩展的状态转换函数
δ *(q,ε )=q δ *(q,a)=δ (q,a) 其中a∈∑
对于串w=α a（α ∈∑+） δ *（q ， w ） =δ *(q，α a） =δ (δ *(q,α ),a)
或者
对于串w= aα δ *(q，w) =δ *(q，aα ) =δ *(δ (q，a),α )
当将串w扫描结束后， 若DFA处于某一个接收状态， 则有限状态自动机能够接收串w
对于可接收串 DFA 从开始状态开始，在扫描串的 过程中， 状态逐个地变化,串扫描结束后， 处于某个接收状态。
对于不可接收串 DFA 从开始状态开始，在扫描串的 过程中， 状态逐个地变化,串扫描结束后， 处于某个非接收状态。
使用=>*代表格局的任意次转换 使用=>+代表格局的多次转换
可以使用格局的转换方式定义FSL
DFA接收的语言 L(DFA)= {w|q0w=>*qfε ；w∈∑*且qf∈F}
定义3-8 DFA停机
DFA将输入串扫描结束时
(自动)停机 这是DFA唯一的停机情况
注意1：
DFA将输入串扫描结束停机时， 如果DFA处于某一个接收状态， 则表示接收整个输入串； 反之，则表示不接收整个输入串;
DFA的接收状态的作用
证明
假设L是字母表∑上的FSL，则 L=L(DFA)
DFA=（Q，∑，δ ，q0，F） 构造右线性文法G=(∑,Q,q0，P） 其中P为：
{q→aq′|δ (q，a)=q′} U{ q→a|δ (q，a)∈F } 特别，若q0是接收状态，则 q 0 →ε
对于句子w=x1x2…xn
一个有穷状态控制器（FSC） 该控制器的状态只能是有限多个 FSC通过读头读取当前带上单元 的字符。
初始时，读头对应带的最左 单元，每读取一个字符，读头 向右自动移动一个单元。 读头（暂时）不允许向左移动。
有限状态自动机的一个动作为： 读头读取带上当前单元的字符 FSC根据当前FSC的状态和读取 的字符，进行状态改变； 将读头向右移动一个单元。
结论:DFA状态等价于文法非终结符 状态转换函数等价于产生式
构造文法的基本思路：
将的DFA的状态当作是RLG的非终结
符(开始状态就是开始符号) 对于某个句子： DFA通过状态的改变，逐步（自左向 右）接收句子的每个字母； RLG通过非终结符号的改变，逐步 （自左向右）产生句子的每个字母。
思考
例3-2 DFA与文法的转换
FSL={(0,1)1*0}* 接收该语言的DFA为：
1
q0 0 0 q1 1
构造正则文法产生该语言： q0→0q1|1q1|ε q1→0q0|1q1| 0
定理3-2
FSL对补运算封闭
证明：
设L1是∑上的FSL,且L1=L(DFA1)， DFA1=（Q，∑，δ ，q0，F）
在扫描串的过程中，格局在发 生转换(改变) 格局的 ( 一次 ) 转换的原因是由 于δ 函数的(一次)作用
如果当前格局为：qar 有δ 函数：δ (q，a)= q′ 则下一格局为： q′r 格局的转换可以记为： qar => q′r
DFA的特殊格局
初始格局为： q0w 接收格局为： qfε 其中，qf是某个接收状态
第三章
有限状态自动机
定义语言
可以从两个方面进行： １）从产生语言的角度； ２）从接收(或识别)语言的角度。
形式语言研究内容
产生一个语言: 1)定义语言中的基本句子; 2)根据其余句子的形成规则，产生 出该语言所包含的所有句子。
有限自动机研究内容
使用某种自动机模型来接收字符串 接收的所有字符串形成的集合，也 是一个语言
统一的理论
形式语言与自动机作为统一的理论,实 际上包括3个方面的内容: 1) 形式语言理论(文法产生语言) 2) 自动机理论(自动机接收语言) 3) 形式语言与自动机的等价性理论 (文 法与自动机等价转换)
有限自动机分为3类
有限状态自动机FA
下推自动机PDA
图灵机TM
有限状态自动机 FA (Finite state Automaton)
用状态图表示一个DFA 有向边的数目就是状态转换函数 的个数。
默认有 δ (q,ε )=q 但不是状态转换函数
why?
3.2 有限状态自动机接收语言 对于DFA，给定串w=x1x2„xn 初始时， DFA处于开始状态q0 从左到右逐个字符地扫描串w
在δ (q0，x1)= q1的作用下 DFA处于状态q1 在δ (q1，x2)=q2的的作用下 DFA处于状态q2 …
因此，在确认输入串包含000后， 就可以逐一地读入 000 后面的全 部字符，并接收该输入串。
思考 问题的关键是？ 如何发现子串000。
由于字符是逐一读入的，当从输入 串中读入一个0时， 它有可能是000的第1个0， 需要记住已经出现过一个0；
如果紧接着读入的是字符1， 则刚读入的0就不是000的第1个0 需要重新寻找000子串的第1个0；
构造
DFA2=（Q，∑，δ ，q0，Q） DFA2接收的语言是 L1的对应的全集,即∑*
构造 DFA3=(Q，∑，δ ，q0，Q-F) L3=L(DFA3) L3接收的语言是L1(关于∑*)的补 L3也是FSL语言。
注意
此时的DFA1的δ 函数的个数为 |Q|*|∑|
基本的等价替换
对于状态转换图，有基本的等价替换
定义3-6
DFA接收的语言
DFA=(Q,∑,δ ,q0，F)接收的语言 L(DFA)={w|δ *(q0,w)∈F}
思考
如何描述 在某个时刻，DFA所处的情况？
定义3-7 DFA的瞬时描述（格局） 格局是一个二元式：qy q是DFA当前状态 y是输入带上还没有被扫描到的串 读头将扫描y串的第1个字母
对于字母表∑上的DFA 能够接收的所有串的集合，就是 DFA能接收的语言，记为L(DFA) 也称为有限状态语言（FSL）
思考
如何形式化定义L(DFA)?
定义3-4 扩展的状态转换函数
给定DFA，扩展的状态转换函数 δ *：Q×∑*→Q 即 δ *(q,w)=q′ 即 DFA 在一个状态 q 时，扫描串 w 后 到达唯一确定的状态q′
例3-4构造DFA
接收语言L={x000y|x,y∈{0,1}*}
分析
该语言的特点是 语言中的每个串都包含连续的 3 个0（即每个串都包含子串000）
因此，对于任何输入串，有限状 态自动机的任务就是要检查该输入 串中是否存在子串000， 一旦发现输入串包含有 000 ，则 表示整个输入串是句子。
FA是为研究
有限存储的机制 和 正则语言 而抽象出的一种模型。
两类有限状态自动机
接收器 判断是否接收输入串； 转换器 对给定输入串产生输出。
FA还可以分为
确定的FA----DFA Deterministic Finite state Automaton 非确定FA---- NFA
Non-deterministic Finite state Automaton
…
定理3-1
每个FSL都是一个右线性语言 分析： 已知 接收FSL的DFA 需要 构造RLG，使得 L(RLG)=FSL
等价思路
DFA最重要的部分是状态转换函数 文法最重要的部分是产生式 状态转换函数和产生式是等价的 可以将状态转换函数改造为产生式
等价思路
状态转换函数和产生式的等价作用 δ(q, a)=q′ A→aB 接收a 产生a 状态变化 非终结符号变化
0 1

变换为
0,1
3.3
DFA接收语言的例子
构造DFA，接收语言 L={ab}
基本结构（接收基本句子）
q0
a
q1
b
q2
增加陷阱状态后的DFA
a q0 b
q1
b
a
a, b qt
q2
a, b
思考1 如果将该 DFA 的所有状态都设置 为接收状态(包括陷阱状态)， 接收的语言是？
思考2 如果将该自动机的接收状态和非 接收状态对调 接收的语言是？
注意2：
对于状态q,如果不能接收字母a 则将状态转换到一个特殊的状态： 陷阱状态qt
陷阱状态qt不能够改变为其他状态 即 对于a ∈∑ δ(qt ，a)=qt qt不能够接收任意字母
构造DFA，分别接收语言 ε 、0、01、 0*、 0+ (0+1)*、(0+1)+ 01*0 、1 *00(0+1) * (0+1) *00(0+1) * 0(0+1) *1 0(0+1) *0+1(0+1)*1
有限态自动机的动作可以简化为： FSC根据 当前状态 和 当前读取的带上字符 进行状态改变。
定义3-1 有限状态自动机FA FA是一个五元式 FA=(Q，∑，δ，q0，F) Q是有限状态的集合 ∑是字母表，即输入带上的字 符集合
q0∈Q是开始状态 FQ是接收状态(终止状态)集合
δ是Q×∑→Q的状态转换函数 即δ(q，x)= q′ 代表FA在状态q时，扫描字符x后 状态改变为q′（也称到达状态q′ ）
如果紧接着读入的还是 0 ，它有可能是 000的第2个0， 也需要记住这个0， 继续读入字符，若是0，则发现000 否则，需要重新寻找000。
初始状态：q0
接收0，到达状态q1
接收00 ,到达状态q2
接收000,到达状态q3
因此，基本的状态转移函数为： δ (q0，0)=q1 δ (q1，0)=q2 δ (q2，0)=q3 用于接收基本句子000
分析：
对于任何输入串，DFA的任务就 是要检查该输入串中是否存在001
δ的表示：状态矩阵
Q