第六章 有限状态自动机和有限状态语言 已经介绍过从产生语言的角度定义语言的 形式;下面从识别语言的角度来定义语言 有限状态自动机(FsM“ finite state machine”或者FSA“ finite state automaton)是为研究有限内存的计算过 程和某些语言类而抽象出的一种计算模型
第六章 有限状态自动机和有限状态语言 ⚫ 已经介绍过从产生语言的角度定义语言的 形式；下面从识别语言的角度来定义语言。 ⚫ 有限状态自动机(FSM “finite state machine” 或者FSA “finite state automaton”)是为研究有限内存的计算过 程和某些语言类而抽象出的一种计算模型
有限状态自动机拥有有限数量的状态,每 个状态可以迁移到零个或多个状态,输入 字串决定执行哪个状态的迁移。有限状态 自动机可以表示为一个有向图(称之为状 态转换图)
⚫ 有限状态自动机拥有有限数量的状态，每 个状态可以迁移到零个或多个状态，输入 字串决定执行哪个状态的迁移。有限状态 自动机可以表示为一个有向图(称之为状 态转换图)
●有限状态自动机是自动机理论的研究对象。 ●有多种类型的有限状态自动机:接受器判 断是否接受输入;转换器对给定输入产生 个输出。常见的转换器有 Moore机与 Meay机。 Moore机对每一个状态都附加 有输出动作,Meay机对每一个转移都附 加有输出动作
⚫ 有限状态自动机是自动机理论的研究对象。 ⚫ 有多种类型的有限状态自动机：接受器判 断是否接受输入；转换器对给定输入产生 一个输出。常见的转换器有Moore机与 Mealy机。Moore 机对每一个状态都附加 有输出动作，Mealy 机对每一个转移都附 加有输出动作
●有限状态自动机还可以分成确定与非确定 两种。非确定有限状态自动机可以转化为 确定有限状态自动机。 有限状态自动机识别的语言是正则语言 RL。 ●有限状态自动机除了它在理论上的价值, 还在数字电路设计、词法分析、文本编辑 器程序等领域得到了应用
⚫ 有限状态自动机还可以分成确定与非确定 两种。非确定有限状态自动机可以转化为 确定有限状态自动机。 ⚫ 有限状态自动机识别的语言是正则语言 RL。 ⚫ 有限状态自动机除了它在理论上的价值， 还在数字电路设计、词法分析、文本编辑 器程序等领域得到了应用
6.1有限状态自动机 有穷状态自动机是具有离散输入和输出的系统的 种数学模型。其主要特点有以下几个方面: (1)系统具有有穷个状态,不同的状态代表不同的 意义。按照实际的需要,系统可以在不同的状态 下完成规定的任务。 ●(2)我们可以将输入字符串中出现的字符汇集在 起构成一个字母表。系统处理的所有字符串都是 这个字母表上的字符串
6.1 有限状态自动机 ⚫ 有穷状态自动机是具有离散输入和输出的系统的 一种数学模型。其主要特点有以下几个方面： ⚫ (1)系统具有有穷个状态，不同的状态代表不同的 意义。按照实际的需要，系统可以在不同的状态 下完成规定的任务。 ⚫ (2)我们可以将输入字符串中出现的字符汇集在一 起构成一个字母表。系统处理的所有字符串都是 这个字母表上的字符串
(3)系统在任何一个状态下,从输入字符串中读 入二个字符,根据当前状态和读入的这个字符 转到新的状态。 ●(4)系统中有一个状态,它是系统的开始状态。 (5)系统中还有一些状态表示它到目前为止所读 入的字符构成的字符串是语言的一个句子 ●有限状态自动机物理模型如图6-1所示
⚫ (3)系统在任何一个状态下，从输入字符串中读 入一个字符，根据当前状态和读入的这个字符 转到新的状态。 ⚫ (4)系统中有一个状态，它是系统的开始状态。 ⚫ (5)系统中还有一些状态表示它到目前为止所读 入的字符构成的字符串是语言的一个句子 ⚫ 有限状态自动机物理模型如图6-1所示
个输入存储带,带被分解为单元,每个单元 存放一个输入符号(字母表上的符号),整个 输入串从带的左端点开始存放,而带的右端可 以无限扩充; 个有穷状态控制器(FSC),该控制器的状 态只能是有穷多个;FSC通过一个读头和带上 单元发生耦合,可以读出当前带上单元的字符。 初始时,读买对应带的最左单元,每读出一个 字符,读头向右移动一个单元(读头不允许向 左移动)
⚫ 一个输入存储带，带被分解为单元，每个单元 存放一个输入符号（字母表上的符号），整个 输入串从带的左端点开始存放，而带的右端可 以无限扩充； ⚫ 一个有穷状态控制器（FSC），该控制器的状 态只能是有穷多个；FSC通过一个读头和带上 单元发生耦合，可以读出当前带上单元的字符。 初始时，读头对应带的最左单元，每读出一个 字符，读头向右移动一个单元（读头不允许向 左移动）
有限状态自动机的一个动作为: ●读头读出带上当前单元的字符;FSC根据 当前FSc的状态和读出的字符,改变FSC 的状态;并将读头向右移动一个单元。 有限状态自动机的动作简化为: FSC根据当前的状态和当前带上的字符, 进行FSC状态的改变
⚫ 有限状态自动机的一个动作为： ⚫ 读头读出带上当前单元的字符；FSC根据 当前FSC的状态和读出的字符，改变FSC 的状态；并将读头向右移动一个单元。 ⚫ 有限状态自动机的动作简化为： ⚫ FSC根据当前的状态和当前带上的字符， 进行FSC状态的改变
定义6-1有限(有穷)状态自动机(接收机) 的定义 母装X已的有限状收(FSAM)是 个五元式,FSAM=(Q,∑,δ,q0,F), ●其中: ●Q是一个有限状态的集合; ●∑是字母表,也就是输入带上的字符的集合; q0∈Q是开始状态 FcQ是接收状态(终止状态)集合
定义6-1 有限（有穷）状态自动机（接收机） 的定义 ⚫ 字母表∑上的有限状态接收机（FSAM）是 一个五元式，FSAM=（Q，∑，δ，q0，F）， ⚫ 其中： ⚫ Q是一个有限状态的集合； ⚫ ∑是字母表，也就是输入带上的字符的集合； ⚫ q0∈Q是开始状态； ⚫ FСQ是接收状态（终止状态）集合；
δ是Q×∑→Q的状态转换函数,即(q x)=g;,代表自动机在状态q时,扫描字符 x后到达状态q。 ●理论上,有限状态自动机的状态转换函数 的个数应该为Q∑。因为对于Q中的每 个状态,都应该定又扫描字母表∑上的每 个字母的状态转换函数
⚫ δ是Q×∑→Q的状态转换函数，即δ(q， x)= q′；代表自动机在状态q时，扫描字符 x后到达状态q′。 ⚫ 理论上，有限状态自动机的状态转换函数 的个数应该为|Q|*|∑|。因为对于Q中的每 个状态，都应该定义扫描字母表∑上的每 个字母的状态转换函数