【编译原理】有限状态机（FSM）和有限自动机（FA） |
您所在的位置：网站首页 › 编译原理有限自动机最小化 › 【编译原理】有限状态机（FSM）和有限自动机（FA） |
【编译原理】有限状态机（FSM）和有限自动机（FA）
|
1 回顾
1.1 一些基本概念
程序：特定符号的字符串 语法：通过使用它来生成格式良好的程序的一组规则 1.2 基本功能与层次程序：描述对某些数据的处理过程 程序语言的功能：描述数据和数据的处理过程 程序层次： 子程序，过程，函数面向对象：类句子：表达式 2 一些基本术语 2.1 字母表一组非空有限元（符号），我们写为∑ {a, b, c, +, …} 2.2 字符串表中每个元素都称为string ∑中的字符串：由∑中的符号组成的任何有限序列 空序列：不包含任何字符串的序列（空字符串ε，也是∑的字符串） ∑*，所有字符串，包括ε（∑不包括ε） 也称为有限自动机（FA） 它用来表达第三类语法（正则语法） 这种语法所描述的语言是正则语言（一种语言可以用正则语法来描述，那么就可以用FSM来分析） Transition states: 根据一个或多个标记字符的匹配，记录从一个状态到另一个状态的更改。 Accepting（final）states: 表示识别过程的结束 在图中的状态周围绘制双线边框 有限自动机（有限状态机）是描述特定类型算法的数学方法。 有限自动机与正则表达式之间的强关系。 只要一种语言可以用正则语法来描述，它就可以用FSM来分析。 4 有限状态机和正则表达式之间的关系只要一种语言可以用规则语法来描述，它就可以用FSM来分析 每个FSM只识别一种语言 ε-转变：在不查阅输入字符串（并且不使用任何字符）的情况下可能发生的转换
识别一种语言（可以是字符串集） 
6 有限状态机(FSM)的形式化定义
补充：NFSM =》一个输入对应多个输出 6.1 五元组表示法FSM是一个5元组 M = (S, Σ, f, s0, Z) 其中： S是有限状态集合Σ是一个有限字母表，其中w=w1w1…wn是一个输入字符串，且wi是∑的成员f是一个单值转换函数，定义了S x Σ -> Ss0∈S是初始状态0Z∈S是最终状态 
6.2 状态转换表表示法
语法：描述语言语法结构的形式规则 给出语言定义的三种方法： 列举：限定句 e.g. { I am a teacher, You are students}有限规则：用所描述的语言生成所有句子/有限或无限的句子自动机（一种算法或过程）： 1）字母表中的所有字符串作为输入，检查或识别这些字符串 2）当输入字符串是字母表中的一个句子时，接受 3）否则，拒绝 8 乔姆斯基（Chomsky）类别（层次结构）乔姆斯基将语法分为4个类，每个类对应一种语言 Type 0 grammar Type 1 grammar Type 2 grammar Type 3 grammar 表达能力不断增强的形式语法类型集 8.1 类型0（短语结构语法或无限制语法）G中的规则为α→ β、 α∈V+和β∈V*，对α，β没有其他限制 类型0定义的语言：L0或递归可枚举语言 图灵机：接受或识别这种类型的语言 8.2 类型1（上下文有关语法）G中的规则为α1Aα2→α1βα2，α1，α2∈V+，A∈Vn，β∈V+ (A是非终结符) 终结字符指的是不可再分解的字符 类型1定义的语言:L1或上下文有关语言 线性有限自动机：接受或识别这种类型的语言 8.3 类型2（上下文无关语法）G中的规则为A→β、 A∈Vn，β∈V+ 类型2定义的语言：L2或上下文无关语言 下拉机（pumping lemma）：接受或承认这类语言 8.4 类型3（正则语法）G中的规则为 A→aB or A→a, A and B ∈Vn, a∈Vt A→Ba or A→a, A and B ∈Vn, a∈Vt 类型3定义的语言：L3或正则语言 有限自动机：接受或识别这种类型的语言 8.5 总结
举例：如果语法是正则的，那么它必须是上下文无关 |
字符串的长度：字符串中symbol的数量 
Start（initial）state： 识别过程开始 画一条“不知从何而来”的无标记箭头线
每个FSM只识别一种语言
L0 L1 L2 L3 从左到右，最右边语法限制最多 if α → β Type 0 grammar: at least one non-terminal in α Type 1 grammar: |α| ≤ |β| Type 2 grammar: A∈ Vn Type 3 grammar: A → wB or A → Bw
参考来源：Dr. Amit K. Chopra【本文地址】
今日新闻 |
推荐新闻 |