有限自动机的原理及示例

1、计算机组成原理与结构期末论文有限自动机的原理及示例 学院： 专业： 姓名： 学号： 有限自动机的原理及示例本文将介绍几种重要有限自动机的基本原理，并通过例子说明它们的运行过程。一 语言的基本概念一张字母表是一个非空有限集合，字母表中的每个元素称为中的一个字母，也称符号、终止符或者字符。中有限个字符有序地排列起来就称为上的一个字符串，称为它的长度。其中有一个特殊的串，它的长度为零。若和都是字母表，则它们的乘积定义为，特别地，令若，且则称是的子串。 字母表上的一种语言是的一个子集。二 有限状态自动机的原理和运算实例1.基本原理一个有限状态自动机的物理模型通常包括两部分：（1）一个输入存储带，带被分

2、解为多个单元，每个单元存放一个输入符号（字母表上的符号），整个输入串从带的左端点开始存放，而带的右端可以无限扩充。 （2）一个有限状态控制器（FSC）,该控制器的状态只能是有限个；FSC通过一个读头和带上单元发生耦合，可以读出当前带上单元的字符。初始时，读头对应带的最左单元，每读出一个字符，读头向右移动一个单元。 有限状态自动机的一个动作为：读头读出带上当前单元的字符；FSC根据当前FSC的状态和读出的字符，改变FSC的状态；并将读头右移一个单元。接着给出有限状态自动机的数学模型。字母表上的一个有限状态自动机(FSAM)是一个五元组其中，i)是一个有限状态的集合；ii)是字母表，它是输入带上的

3、字符的集合； iii)是开始状态； iv)是接收状态（终止状态）集合； v)是状态转换函数，表示自动机在状态时，扫描字符后到达状态。对于有限状态自动机，给定字母表上的串；初始时，自动机处于开始状态；从左到右逐个字符地扫描串；在的作用下，自动机处于状态，在的作用下，自动机处于状态，当将串扫描结束后，若自动机处于某一个接收状态，则称有限状态自动机能够接收（识别）串。对于自动机而言，从开始状态开始，在扫描串的过程中，状态逐个地变化，直到某个接收状态，把状态的变化过程称为自动机的一条路径，而这条路径上所标记的字符的连接，就是自动机所识别的串。有时为了表述方便，也采用如下定义的扩展的状态转换函数即自动机

4、在一个状态时，扫描串后到达唯一确定的状态；换句话说，如果是一个字母，是一个字符串，那么并且对串，. 用表示被接收的语言，它在字母表上，即，则. 若语言对某个自动机有，则称语言为一个有限状态语言。 有限状态自动机的瞬时描述是一个二元组，其中是输入带上还没有被扫描到的字符串，FSC的当前状态为，读头将马上扫描串的左边第一个符号。有限状态自动机的初始格局为，接收格局为，其中是初始状态，是某个接收状态。 有限状态自动机在下面两种情形下停机：（1） 输入串扫描结束时；（2） 有限状态自动机的当前格局为，而自动机没有对应的函数的定义，即没有定义。在这种情形，可以补充定义一个特殊的状态：陷阱状态，即。对于陷

5、阱状态，对任何字母，定义.2.两个例子例2.1 我们将构造一个有限状态自动机，它能识别上的语言.分析：语言的特点是语言中的每个串都包含连续的3个0，故FSC的状态及其意义如下：（1）：有限状态自动机的开始状态，也是重新寻找子串000时的状态；（2）：有限状态自动机读到第一个0，有可能是子串000的第一个0；（3）：有限状态自动机在后又读到一个0；（4）：有限状态自动机在后又读到一个0，这是唯一的接收状态。因此，状态转移函数为接收状态为.例2.2 构造有限状态自动机，识别上的语言，该语言的每个字符串看成二进制数时，代表的数字能整除3.分析：使用3个状态分别代表已经读入的数除以3的得到不同余数的等

6、价类：（1）：已经读入的数除以3，余数为0的输入串的等价类；（2）：已经读入的数除以3，余数为1的输入串的等价类；（3）：已经读入的数除以3，余数为2的输入串的等价类；因为不能接收空串，所以还需要一个开始状态。设是当前读入的输入串，则（1）：在开始状态读入0时，有，进入状态；读入1时，有，进入状态。（2）：能引导自动机到达此状态的是3的倍数，因此。 a)在此状态读入0，引导自动机到达下一状态的输入串为，则，这表明也属于对应的等价类。所以自动机在状态读入0应该继续保持状态。 b)在此状态读入1，引导自动机，到达下一状态的输入串为，则，这表明属于对应的等价类。所以自动机在状态读入1应该进入状态。(

7、3): 能引导自动机到达此状态的满足。a)在此状态读入0，引导自动机到达下一状态的输入串为，则，这表明属于对应的等价类。所以自动机在状态读入0进入状态。b)在此状态读入1，引导自动机到达下一状态的输入串为，则，这表明属于对应的等价类。所以自动机在状态读入1进入状态。（4）：能引导自动机到达此状态的满足。 a)在此状态读入0，引导自动机到达下一状态的输入串为，则，这表明属于对应的等价类。所以自动机在状态读入0进入状态。b)在此状态读入1，引导自动机到达下一状态的输入串为，则，这表明属于对应的等价类。所以自动机在状态读入1继续保持状态。因此状态转换函数为接收状态为。三 带输出的有限状态自动机1.

8、Moore机的原理Moore机的数学模型是一个六元组其中 1）的含义同有限状态自动机。 2）是输出字母表。 3）是输出函数。对于，表示Moore机在状态时输出。 Moore机在读入输入串的过程中，状态不断发生改变，并且在每个状态上都有输出。 对于输入串序列，Moore机的输出序列为这里因此，如果输入串的长度为，那么Moore机的输出串的长度为。2. Moore机的运算示例例3.1 构造一个Moore机，若将输入串当作一个二进制数，则在读入串的过程中，希望输出已经读过的子串模3的余数。分析：因为模3的余数只有0、1和2，所以输出字母表，并设3个状态（1）：已经读入的数除以3，余数为0的输入串的等

9、价类；（2）：已经读入的数除以3，余数为1的输入串的等价类；（3）：已经读入的数除以3，余数为2的输入串的等价类；像例2.2那样，状态转换函数为根据状态转换函数的结果，输出函数为 例如当输入空串时，输出余数为0；当输入1010时，状态变换的序列为对应的输出序列为01221。3. Mealy机的原理Mealy机的数学模型是一个六元组其中1）的含义同有限状态自动机。 2）是输出字母表。 3）是输出函数。对于，表示Moore机在状态，读入字母时，输出。 Mealy机在读入串的过程中，状态不断发生改变，并且在每个状态上，读入某个字母时，Mealy机都有输出。 对于输入串序列，Mealy机的输出序列为这里因此，如果输入串的长度为，那么Moore机的输出串的长度也为。4. Mealy机的运算示例例3.2 构造一个只有两个输出符号的Mealy机，对于上的语言，当读过的输入串属于时，Mealy机输出，表示接收；当读过的输入串不属于时，Mealy机输出，表示拒绝。分析：定义3个状态（1）：开始状态。（2）：自动机读入的字符是0。（3）：自动机读入的字符是1。那么（1）：若即将读入0，则自动机进入状态，同时输出；若即将读入1，则自动机进入状态，同时输出。（2）：若即将读入0，则自动机保持状态，同时输出；若即将读入1，则自动