自动机与形式语言 报告人：姜勇刚 郑奘巍.

Presentation on theme: "自动机与形式语言 报告人：姜勇刚 郑奘巍."— Presentation transcript:

1 自动机与形式语言 报告人：姜勇刚 郑奘巍

2 电视是一个自动机 从“关机状态”开始，给出一个操作序列，如： “按下开关”、“按下开关”、“按下开关”
从左到右执行操作序列 → 得到终止状态： “开机状态” 按下开关 关机状态 开机状态 按下开关

3 确定有限状态自动机 一个确定有限状态自动机（DFA "deterministic finite automaton"）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F) 有穷状态集合 Q ； 有穷输入字母表 Σ； 转移函数 δ: Q × Σ -> Q； 初始状态 q0； 终结状态集合 F，F 包含于 Q 。

4 确定有限状态自动机 状态集合 状态转移规则 初始状态 进行替换：关机状态→1，开机状态→2 按下开关→a 按下开关 关机状态 开机状态

5 确定有限状态自动机 a 1 2 a 状态集合：{1 , 2} 初始状态：1 状态转移规则：1×a→2 , 2×a→1
任意给出一个操作序列，可以得到一个终止状态： aaa→2 aaaaaa→1

6 用有限状态自动机来描述形式语言 如果把一些状态定义为“可接受的终止状态”，并且当一个输入序列得到的 终止状态为“可接受的终止状态”时，我们说这个序列被接受了。 a 规定2为可接受终止状态 1 2 a 输入a*,长度为奇数时，被接受。长度为偶数时，不被接受。 这说明，这个有限状态自动机可以用来表示这样的一种语言： {仅由a构成的字符串，且长度为奇数} 只有当输入字符串被自动机接受时，才说这种字符串是合法的语言。

7 ab* b a,b a 1 2 a 3 b 1为空字符串，符合条件。 3为“死胡同”，进入这个状态以后无论输入什么，都不能进入2。

8 (ac+b)* c a a 1 2 3 c b b a,b,c

9 确定有限状态自动机 一个确定有限状态自动机（DFA "deterministic finite automaton"）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F) 有穷状态集合 Q ； 有穷输入字母表 Σ； 转移函数 δ: Q × Σ -> Q； 初始状态 q0； 终结状态集合 F，F 包含于 Q 。

10 所以：用有限自动机可以用来表示一种语言 有限自动机是一个有向图，这个有向图可以用来判断一 个语句是不是合法的语言
可以证明，任意正则表达式可以用一个有限状态自动机 来表示,任意有限状态自动机都可以表示一个正则表达 式。 这意味着，有限自动机和正则表达式是等价的

11 DFA和正则表达式的转化 a* a+b ab a a b b a 等价性证明思路：递归构造法

12 “形式语言”的重点是“形式”，这种形式可以被严格的识别而不会产生。严格的语言可以用自动机来表示，这意味着计算机也可以准确的理解并识别这种语言

13 用程序实现DFA 用一个有向图来表示DFA，图中每一个节点表示一个状态， 每一条有向边表示一个状态转移规则 对终止节点做特殊的标记
每一个节点的出度都等于字母表中元素个数，因此用邻接 链表来表示图，节点的第i条边表示从这个节点输入第i个字 母后转移到的节点

14 (ac+b)* c a a 1 2 3 c b b a,b,c

15 自动机的应用——字符串匹配算法（KMP）
给出文本串T，模板串P，找出T中所有与P相同的子串 构建模板串P的自动机，状态为“已经匹配的字符个数”，状态数为|P|。匹配失败时状态转移。

16 模板串“abaa”的自动机 b b b a a a 1 2 3 4 b b a a