第六章 有限状态自动机和有限状态语言 已经介绍过从产生语言的角度定义语言的 形式;下面从识别语言的角度来定义语言 有限状态自动机(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)我们可以将输入字符串中出现的字符汇集在一 起构成一个字母表。系统处理的所有字符串都是 这个字母表上的字符串