自动机与形式语言 报告人：姜勇刚 郑奘巍
电视是一个自动机 从“关机状态”开始，给出一个操作序列，如： “按下开关”、“按下开关”、“按下开关” 从左到右执行操作序列 → 得到终止状态： “开机状态” 按下开关 关机状态 开机状态 按下开关
确定有限状态自动机 一个确定有限状态自动机（DFA "deterministic finite automaton"）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F) 有穷状态集合 Q ； 有穷输入字母表 Σ； 转移函数 δ: Q × Σ -> Q； 初始状态 q0； 终结状态集合 F，F 包含于 Q 。
确定有限状态自动机 状态集合 状态转移规则 初始状态 进行替换：关机状态→1，开机状态→2 按下开关→a 按下开关 关机状态 开机状态
确定有限状态自动机 a 1 2 a 状态集合：{1 , 2} 初始状态：1 状态转移规则：1×a→2 , 2×a→1 任意给出一个操作序列，可以得到一个终止状态： aaa→2 aaaaaa→1
用有限状态自动机来描述形式语言 如果把一些状态定义为“可接受的终止状态”，并且当一个输入序列得到的 终止状态为“可接受的终止状态”时，我们说这个序列被接受了。 a 规定2为可接受终止状态 1 2 a 输入a*,长度为奇数时，被接受。长度为偶数时，不被接受。 这说明，这个有限状态自动机可以用来表示这样的一种语言： {仅由a构成的字符串，且长度为奇数} 只有当输入字符串被自动机接受时，才说这种字符串是合法的语言。
ab* b a,b a 1 2 a 3 b 1为空字符串，符合条件。 3为“死胡同”，进入这个状态以后无论输入什么，都不能进入2。
(ac+b)* c a a 1 2 3 c b b a,b,c
确定有限状态自动机 一个确定有限状态自动机（DFA "deterministic finite automaton"）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F) 有穷状态集合 Q ； 有穷输入字母表 Σ； 转移函数 δ: Q × Σ -> Q； 初始状态 q0； 终结状态集合 F，F 包含于 Q 。
所以：用有限自动机可以用来表示一种语言 有限自动机是一个有向图，这个有向图可以用来判断一 个语句是不是合法的语言 可以证明，任意正则表达式可以用一个有限状态自动机 来表示,任意有限状态自动机都可以表示一个正则表达 式。 这意味着，有限自动机和正则表达式是等价的
DFA和正则表达式的转化 a* a+b ab a a b b a 等价性证明思路：递归构造法
“形式语言”的重点是“形式”，这种形式可以被严格的识别而不会产生。严格的语言可以用自动机来表示，这意味着计算机也可以准确的理解并识别这种语言
用程序实现DFA 用一个有向图来表示DFA，图中每一个节点表示一个状态， 每一条有向边表示一个状态转移规则 对终止节点做特殊的标记 每一个节点的出度都等于字母表中元素个数，因此用邻接 链表来表示图，节点的第i条边表示从这个节点输入第i个字 母后转移到的节点
(ac+b)* c a a 1 2 3 c b b a,b,c
自动机的应用——字符串匹配算法（KMP） 给出文本串T，模板串P，找出T中所有与P相同的子串 构建模板串P的自动机，状态为“已经匹配的字符个数”，状态数为|P|。匹配失败时状态转移。
模板串“abaa”的自动机 b b b a a a 1 2 3 4 b b a a