电子科技大学：《有限自动机理论 Finite Automata Theory》课程教学资源（课件讲稿）第03章 有限状态自动机

第三章 有限状态自动机

第三章 有限状态自动机

定义语言 可以从两个方面进行： 1)从产生语言的角度； 2)从接收（或识别语言的角度

定义语言 可以从两个方面进行： １）从产生语言的角度； ２）从接收(或识别)语言的角度

形式语言研究内容 产生一个语言： )定义语言中的基本句子； 2)根据其余句子的形成规则，产生 出该语言所包含的所有句子

形式语言研究内容 产生一个语言: 1)定义语言中的基本句子; 2)根据其余句子的形成规则，产生 出该语言所包含的所有句子

有限自动机研究内容 使用某种自动机模型来接收字符串 接收的所有字符串形成的集合，也 是一个语言

有限自动机研究内容 使用某种自动机模型来接收字符串 接收的所有字符串形成的集合，也 是一个语言

统一的理论 形式语言与自动机作为统一的理论，实 际上包括3个方面的内容： 1)形式语言理论（文法产生语言） 2)自动机理论（自动机接收语言） 3)形式语言与自动机的等价性理论（文 法与自动机等价转换)

统一的理论 形式语言与自动机作为统一的理论,实 际上包括3个方面的内容: 1) 形式语言理论(文法产生语言) 2) 自动机理论(自动机接收语言) 3) 形式语言与自动机的等价性理论 (文 法与自动机等价转换)

有限自动机分为3类 ●有限状态自动机FA ●下推自动机PDA 图灵机TM

有限自动机分为3类 l有限状态自动机FA l下推自动机PDA l图灵机TM

有限状态自动机FA (Finite state Automaton) FA是为研究 有限存储的机制 和 正则语言 而抽象出的一种模型

有限状态自动机 FA (Finite state Automaton) FA是为研究 有限存储的机制 和 正则语言 而抽象出的一种模型

两类有限状态自动机 接收器 判断是否接收输入串； 转换器 对给定输入串产生输出

两类有限状态自动机 接收器 判断是否接收输入串； 转换器 对给定输入串产生输出

FA还可以分为 确定的FA--DFA Deterministic Finite state automaton 非确定FA--NFA Non-deterministic Finite state automaton

FA还可以分为 确定的FA----DFA Deterministic Finite state Automaton 非确定FA---- NFA Non-deterministic Finite state Automaton

等价性 有限状态自动机接收的语言称 为有限状态语言-FSL 从产生语言角度而言，FSL就 是右线性语言-RLL 从（正则）运算角度而言， FSL 就是正则语言-RL

等价性 有限状态自动机接收的语言称 为有限状态语言--FSL 从产生语言角度而言， FSL就 是右线性语言--RLL 从(正则)运算角度而言， FSL 就是正则语言--RL