「自动机」第三章

发布于 2022-03-27  201 次阅读


第三章

主要内容

  • 确定有限自动机
  • 非确定有限自动机
  • 确定与非确定有限自动机的等价性
  • 右线性文法和有限自动机的等价性
  • 右线性文法的性质(泵浦定理)
  • 只用归纳法进行证明的方法

第一节 有限自动机

有限自动机的概念

具有离散输入输出系统的一种数学模型(可以没有输出,比较特殊的也可以没有输入)

有限的状态

状态+输入--->状态转移

每次转换的后继状态都唯一 ---> DFA

每次转换的后继状态不唯一 ---> NFA

DFA Deterministic finite automaton

NFA Non Deterministic finite automaton

DFA的形式定义

定义:DFA是一个五元组M=(Q,T,δ,q0,F)

  • Q: 有限的状态集合
  • T: 有限的输入字母表
  • δ: 转换函数(状态转移集合): Q×T ---> Q
  • q0: 初始状态, q0 ∈ Q
  • F: 终止状态集, F ∈ Q

转移图表示的DFA

image-20220321102354220

转移表表示的DFA

image-20220321102418017

扩展转移函数适合于输入字符串

δ’函数:接收一个字符串的状态转移函数。 δ’ : Q x T* ---> Q

对任何q ∈ Q,定义:

1.δ’ (q , e ) = q

2.若ω是一个字符串, a是一个字符,定义: δ’(q,ωa)=δ(δ’(q,ω),a)

对于DFA,δ’(q,a)=δ(δ‘(q, e ),a)=δ(q,a),即对于单个字符时δ和δ'是相等的。为了方便,以后在不引起混淆时用δ代替δ'

被DFA接受的语言

n被DFA接收的字符串: 输入结束后使DFA的状态到达终止状态。否则,该字符串不能被DFA接收.

DFA接收的语言: 被DFA接收的字符串的集合.

L(M) = { ω | δ’ ( q0 , ω) ∈ F }

格局

为描述有限自动机的工作过程,对于它在某一时刻的工作状态,可用两个信息表明:当前状态q,待输入字符串ω。两者构成一个瞬时描述,用(q, ω)表示,称为格局。

初始格局:(q0, ω)

终止格局: (q, ε), q∈F

有限状态机是无记忆的,接受不同的字符串可以进入同一格局

设计有限自动机

自动机的设计是一个创造过程,没有简单的算法或过程。

技巧:假设自己是机器,思考如何去实现机器的任务。

为判断到目前为止所看到的字符串是否满足某个语言,须估算出读一个字符串时需要记住哪些关键的东西。

例1:构造自动机,识别所有由奇数个a和奇数个b组成字符串。

关键:不需要记住所看到的整个字符串,只需记住至此所看到的a、b个数是偶数还是奇数。

第二节 不确定的有限自动机(NFA)

修改DFA的模型,使之在某个状态, 对应一个输入,可以有多个转移, 到达不同的状态, 即:具有同时处于几个状态的能力。则称为不确定的有限自动机。

不确定有限自动机的形式定义

nNFA是一个五元组,M=(Q,T,δ,q0,F).

其中δ是Q×T->2^Q的函数, 其余与DFA相同.

n如果接收一个字符串后NFA进入一个状态集,而此集合中包含一个或以上F中的状态, 则称NFA接收该字符串.

数学上如何表达多个状态呢?使用幂集状态子集。

设X是一个非空集合,由X的一切子集(包括空集,X自身)为元素形成的集合称为X的幂集。有n个元素形成的集合的幂集共有2的n次方个元素。

转移图和转移表表示的NFA

格局示例

n如图所示,用格局序列描述自动机的工作过程,当输入字符串是011011时,则有

NFA的状态扩展函数

δ可扩展为δ’ (δ’ : Q x T* ---> 2^Q)

1.δ'(q, ε) = {q} 含义: 不允许无输入的状态变化.

2.δ'(q,ωa)={p|存在r∈δ'(q,ω)∧p∈δ(r,a)}

含义:δ‘(q,ωa)对应的状态集合是δ’(q,ω)对应的每个状态下再接收字符a以后可能到达的状态集合的并集.

NFA接受的语言

设一个 NFA A = (Q, T, d, q0 , F )

定义 A 的语言:

L(A) = { ω | δ' ( q0 , ω) ∩ F != ∅ }

第三节 NFA与DFA的等价性

DFA是NFA的特例(DFA本身就是NFA), 所以NFA必然能接收DFA能接收的语言. 因此证明等价性只要能够证明一个NFA所能接收的语言必能被另一个DFA所接收。

定理: 设一个NFA接受语言L, 那么必然存在一个DFA接受L。

证明:

策略:对于任意一个NFA,构造一个接收它所能接收语言的DFA,这个DFA的状态对应了NFA的状态集合。

步骤:

  1. 初始的NFA
  2. 子集构造,计算状态可达
  3. 经筛选后的DFA

证明:从NFA构造等价的DFA