《【计算机】形式语言06章有限状态自动机和有限状态语言》由会员分享，可在线阅读，更多相关《【计算机】形式语言06章有限状态自动机和有限状态语言（138页珍藏版）》请在金锄头文库上搜索。
1、 第六章有限状态自动机和有限状态语言l已经介绍过从产生语言的角度定义语言的 形式；下面从识别语言的角度来定义语言 。l有限状态自动机(FSM “finite state machine” 或者FSA “finite state automaton”)是为研究有限内存的计算过 程和某些语言类而抽象出的一种计算模型 。l有限状态自动机拥有有限数量的状态，每 个状态可以迁移到零个或多个状态，输入 字串决定执行哪个状态的迁移。有限状态 自动机可以表示为一个有向图(称之为状态 转换图)。l有限状态自动机是自动机理论的研究对象 。 l有多种类型的有限状态自动机：接受器判 断是否接受输入；转换器对给定输入产
2、生 一个输出。常见的转换器有Moore机与 Mealy机。Moore 机对每一个状态都附加 有输出动作，Mealy 机对每一个转移都附 加有输出动作。 l有限状态自动机还可以分成确定与非确定 两种。非确定有限状态自动机可以转化为 确定有限状态自动机。 l有限状态自动机识别的语言是正则语言RL 。 l有限状态自动机除了它在理论上的价值， 还在数字电路设计、词法分析、文本编辑 器程序等领域得到了应用。6.1 有限状态自动机l 有穷状态自动机是具有离散输入和输出的系统的 一种数学模型。其主要特点有以下几个方面：l(1)系统具有有穷个状态，不同的状态代表不同的 意义。按照实际的需要，系统可以在不同的状
3、态 下完成规定的任务。l(2)我们可以将输入字符串中出现的字符汇集在一 起构成一个字母表。系统处理的所有字符串都是 这个字母表上的字符串。l(3)系统在任何一个状态下，从输入字符串中读 入一个字符，根据当前状态和读入的这个字符转 到新的状态。l(4)系统中有一个状态，它是系统的开始状态。l(5)系统中还有一些状态表示它到目前为止所读 入的字符构成的字符串是语言的一个句子l有限状态自动机物理模型如图6-1所示。l一个输入存储带，带被分解为单元，每个单元存 放一个输入符号（字母表上的符号），整个输入 串从带的左端点开始存放，而带的右端可以无限 扩充；l一个有穷状态控制器（FSC），该控制器的状态
4、只能是有穷多个；FSC通过一个读头和带上单元 发生耦合，可以读出当前带上单元的字符。初始 时，读头对应带的最左单元，每读出一个字符， 读头向右移动一个单元（读头不允许向左移动） 。l有限状态自动机的一个动作为：l读头读出带上当前单元的字符；FSC根据 当前FSC的状态和读出的字符，改变FSC 的状态；并将读头向右移动一个单元。l有限状态自动机的动作简化为：l FSC根据当前的状态和当前带上的字符 ，进行FSC状态的改变。定义6-1 有限（有穷）状态自动机（接收机 ）的定义l 字母表上的有限状态接收机（FSAM）是 一个五元式，FSAM=（Q，q0，F），l其中：lQ是一个有限状态的集合；l是字
5、母表，也就是输入带上的字符的集合；lq0Q是开始状态；lFQ是接收状态（终止状态）集合；l是QQ的状态转换函数，即(q， x)= q；代表自动机在状态q时，扫描字符 x后到达状态q。l理论上，有限状态自动机的状态转换函数 的个数应该为|Q|*|。因为对于Q中的每 个状态，都应该定义扫描字母表上的每 个字母的状态转换函数。l例6-2 有限状态自动机FSAM=（ q0，q1 ，0，1，q0，q0），其中为：l表示为函数形式：l(q0，0)=q1；(q0，1)=q1；l(q1，0)= q1；(q1，1)= q0；l或者表示为状态矩阵的形式。如图6-2所 示。lQ 0 1lq0 q1 q1lq1 q1
6、 q0l l或者表示为状态图的形式。如图6-3所示。l状态图是一个有向、有循环的图。一个节点 表示一个状态；若有(q，x)= q，则l状态q到状态q有一条有向边，并用字母x作 标记。l一个圆圈代表一个状态，指向的状 态是开始状态，两个圆圈代表的状态是接 收状态；在比较明确的情况下，可以用状 态图表示一个有限状态自动机，而有向边 的数目就是状态转换函数的个数。 6.2 有限状态自动机识别语言l定义6-3 有限状态自动机接收串的定义l对于有限状态自动机M，给定字母表上 的串w=w1w2wn；初始时，自动机M处于开 始状态q0；从左到右逐个字符地扫描串w； 在(q0，w1)= q1的作用下，自动机M
7、处于 状态q1，在(q1，w2)=q2的的作用下，自 动机M处于状态q2，；l当将串w扫描结束后，若自动机处于某一 个接收状态，则称有限状态自动机能够接 收（识别）串w。对于自动机而言，从开 始状态开始，在扫描串的过程中，状态逐 个地变化，直到某个接收状态，我们把状 态的变化过程称为自动机的一条路径，而 这条路径上所标记的字符的连接，就是自 动机所识别的串。l定义6-4 有限状态自动机接收的语言 的定义l对于字母表上的有限状态自动机M ，它能识别的所有串的集合，称为自 动机M能识别的语言。记为L(M)。l定义6-5 扩展的状态转换函数的定义l给定FSAM，定义扩展的状态转换函数 *：Q*Q为：
8、*（q，w）=ql即自动机在一个状态q时，扫描串w后 到达唯一确定的状态q。l定义6-6 扩展的状态转换函数的形式 定义l*（q，）=q；l*（q， x）=（q， x）；其中x是 一个字母；l对于串w=x（x是一个字母，是一 个字符串）；l*（q， w）l=*（q， x）l=（*（q， ），x）；l或者：对于串w= x（x是一个字母 ，是一个字符串）；l*（q， w）l=*（q， x）l=*（q， x），）l定义6-7 FSAM接收的语言的定义lL(M)表示被FSAM=（Q，q0，F ）接收的语言，它在字母表上，即 L(M）*，则lL(M）=w|w*且*（q0， w） F。l若语言L*，对于某
9、个有限状态自 动机M，有L=L(M)，则称语言L为一个 有限状态语言（FSL）。定义6-8 有限状态自动机的瞬 时描述（格局）的定义l瞬时描述是一个二元式：qy；y* ，l其中：ly是输入带上还没有被扫描到的字符 串，FSC当前状态为q，读头将马上扫 描y串的最左边第1个符号。l格局可以发生转换（改变），格局发生转 换的原因是由于函数的一次作用。l如果当前格局为：qar，有函数：(q ，a)= q，则下一格局为： qr ；l格局的转换可以记为：qar = qr；l有限状态自动机初始格局为：q0w；l 接收格局为：ql其中:lq0是开始状态,q是某个接收状态； l使用=*代表格局的多次转换。l也
10、可以使用格局的转换方式定义有限 状态自动机接收的语言。l有限状态自动机接收的语言L(M)=w| q0w =* q；w*且qF。l定义6-9 有限状态自动机停机的定义l有限状态自动机在下面两种情况下停机：l（1）有限状态自动机将输入串扫描结束时，或l（2）有限状态自动机的当前格局为：qar，而有 限状态自动机没有对应的函数的定义，即(q ，a)=？ （此时，一定没有扫描完输入串）注意1：l有限状态自动机停机时，并不一定接 收扫描过的串（已经读入的符号串） ；l有限状态自动机将输入串扫描结束停 机时，如果有限状态自动机处于某一 个接收状态，则表示接收整个串；l有限状态自动机将输入串扫描结束停机时，
11、如果 有限状态自动机没有处于任何的接收状态，则表 示不接收整个输入串；l有限状态自动机没有扫描完整个输入串就停机， 一定不会接收整个输入串；如果此时有限状态自 动机处于某一个接收状态，则说明已经扫描过的 串（是整个串的子串，而不是整个输入串）能够 被有限状态自动机接收。注意2:l有限状态自动机的某个状态q，如果对于字母表 上的字母x没有对应的函数的定义，可以省略 掉该函数；或者定义一个特殊的状态：陷阱状 态qt。l对于陷阱状态，定义(q，x)=qt。l陷阱状态qt，仅仅有入口边，没有出口边，一定 不是开始状态。l此时，函数的个数 = |Q| * |。l定理6-10 每个FSL都是一个右线性语言
12、。l证明思路：l假设L是字母表上的有限状态语言，且 L=L(FSAM），FSAM=（Q，q0，F） ，构造右线性文法G=（，Q，q0，P）（ 将自动机的状态当作是文法的非终结符） ，其中P为：lqxq|（q， x）=qU qx|（q， x）F l特别地，若开始状态也是接收状态， 则有q0；l对于串w=w1w2wn：l自动机M： 则文法有l（q0， w1）=q1 q0w1q1；l（q1， w2）=q2 q1w2q2；l l（qn-2，wn-1）=qn-1 qn-2wn-1qn-1l（qn-1， wn）=qnqn-1wnqn l 或 qn-1wn l （qn是接收状态）l所以l对自动机M： 对文法
13、：l *（q, ）= q q=*ql *（q0， w）F q0=*wlFSL=（0，1）0*1*，接收该语言的有限状态自 动机l构造右线性文法产生该语言：lq00q1|1q1|lq11q0|0q1|1定理 右线性语言对补运算是封 闭的l证明：l假设L1是字母表上的有限状态语言，且 L1=L(FSAM1)，FSAM1=（Q，q0，F），而 FSAM2=（Q，q0，Q）接收的语言是右线 性语言L1的对应的全集。l对L1的补运算得到的语言L2=L(FSAM)， FSAM=（Q，q0，Q-F），所以L2也是 FSL语言（右线性语言）。证毕。l注意：l此时的FSAM1的函数的个数 = |Q| * |；即
14、 需要陷阱状态。l 6.3 有限状态自动机识别语言的例子l例6-12 接收语言L=ab的有限状态自动机思考l如果将该自动机的所有状态都设置为接收 状态（包括陷阱状态），那么，自动机接 收的语言是什么？l 如果将该自动机的接收状态和非接收 状态对调，即将状态S、M、和陷阱状态qt 都设置为接收状态，而将原来的接收状态 F设置为非接收状态，那么，自动机接收 的语言是什么？l 构造有限状态自动机M，识别0，1上 的语言L=x000y|x，y0，1*。l分析：l语言L=x000y|x，y000，1*， 该语言的特点是语言中的每个串都包含连 续的3个0（即每个串都包含子串000），l因此，对于任何输入串，有限状态自动机 的任务就是要检查该输入串中是否存在子 串000，一旦发现输入串包含有000，则表 示输入串是个合法的句子（是属于语言中 的一个串），因此，在确认输入串包含 000后，就可以逐一地读入输入串的后面 的字符，并接收该输入串。l问题的关键是如何发现子串000。l由于字符是逐一读入的，当从输入串 中读入一个0时，它就有可能是000子 串的第1个0，就需要记住这个0；如 果紧接着读入的是字符1，则刚才读 入的0就不是子串000的第1个0，此时 ，需要重新寻找000子串的第1个0；l如果紧接着读入的还是字符0，它就 有可能是000子串的第2个0，也就需 要记住这个0，继续读入字
