全部科目 > 软件评测师 >
2019年下半年 上午试卷 综合知识
第 19 题
知识点 有限自动机  
章/节 程序设计语言知识  
 
 
某个不确定有限自动机(和为初态,为终态)如下图所示,( )是该自动机可识别的字符串(即从初态到终态的路径中,所有边上标记的字符构成的序列)。
 
  A.  baabb
 
  B.  bbaab
 
  C.  aabab
 
  D.  ababa
 
 




 
 
相关试题     程序设计语言的基本成分(数据、运算、控制和传输、过程/函数调用) 

  第13题    2013年下半年  
算术表达式a+(b-c)*d的后缀式是(13) (-、+、*表示算术的减、加.乘运算,运算符的优先级和结合性遵循惯例)。

  第30题    2010年下半年  
软件设计要遵循的基本原则包括(30)。
①模块化 ②抽象 ③封装 ④信息隐蔽

  第32题    2013年下半年  
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数已经排好序,将第i个整数依次和第i-1,i-2,…个整数进行比较,找到应该插入的位置。现采用插入排序算法对6..

 
知识点讲解
· 有限自动机
 
        有限自动机
        有限自动机是一种识别装置的抽象概念,它能准确地识别正规集。有限自动机分为两类:确定的有限自动机和不确定的有限自动机。
        (1)确定的有限自动机(Deterministic Finite Automata,DFA)。一个确定的有限自动机是个五元组:(S,∑,fs0Z),其中:
        ①S是一个有限集合,它的每个元素称为一个状态。
        ②∑是一个有穷字母表,它的每个元素称为一个输入字符。
        ③fS×∑→S上的单值部分映像。fAa=Q表示当前状态为A、输入为a时,将转换到下一状态Q。称QA的一个后继状态。
        ④s0S,是唯一的一个开始状态。
        ⑤Z是非空的终止状态集合,
        一个DFA可以用两种直观的方式表示:状态转换图和状态转换矩阵。状态转换图是一个有向图,简称为转换图。DFA中的每个状态对应转换图中的一个结点;DFA中的每个转换函数对应图中的一条有向弧,若转换函数为fAa)=Q,则该有向弧从结点A出发,进入结点Q,字符a是弧上的标记。
        例如,DFAM1=({s0s1s2s3},{ab},fs0,{s3}),其中f为:
        fs0a)=s1fs0b)=s2fs1a)=s3fs1b)=s2fs2a)=s1fs2b)=s3fs3a)=s3
        与DFAM1对应的状态转换图如下图(a)所示,其中,状态s3表示的结点是终态结点。状态转换矩阵可以用一个二维数组M表示,矩阵元素M[A,a]的行下标表示状态,列下标表示输入字符,M[Aa]的值是当前状态为A、输入字符为a时,应转换到的下一状态。与DFAM1对应的状态转换矩阵如下图(b)所示。在转换矩阵中,一般以第一行的行下标对应的状态作为初态,而终态则需要特别指出。
        
        确定的有限自动机示意图
        对于∑中的任何字符串ω,若存在一条从初态结点到某一终止状态结点的路径,且这条路径上所有弧的标记符连接成的字符串等于ω,则称ω可由DFAM识别(接受或读出)。若一个DFAM的初态结点同时又是终态结点,则空字ε可由该DFA识别(或接受)。DFAM所能识别的语言LM)={ω|ω是从M的初态到终态的路径上的弧上标记所形成的串}。
        例如,对于字符串"ababaa",在上图(a)所示的状态转换图中,识别"ababaa"的路径是s0s1s2s1s2s1s3。由于从初态结点s0出发,存在到达终态结点s3的路径,因此该DFA可识别串"ababaa"。而"abab"和"baab"都不能被该DFA接受。对于字符串“abab“,从初态结点s0出发,经过路径s0s1s2s1s2,当串结束时还没有到达终态结点s3;而对于串"baab",经过路径s0s2s1s3,虽然能到达终态结点s3,但串尚未结束又不存在与下一字符"b"相匹配的状态转换。
        (2)不确定的有限自动机(Nondeterministic Finite Automata,NFA)。一个不确定的有限自动机也是一个五元组,它与确定有限自动机的区别如下。
        ①fS×∑→2s上的映像。对于S中的一个给定状态及输入符号,返回一个状态的集合。即当前状态的后继状态不一定是唯一确定的。
        ②有向弧上的标记可以是ε
        例如,已知有NFAN=({s0s1s2s3},{ab},fs0,{s3}),其中f为:
        fs0a)=s0fs0a)=s1fs0b)=s0fs1b)=s2fs2b)=s3
        与NFAM2对应的状态转换图和状态转换矩阵如下图所示。
        
        NFA的状态转换图和转换矩阵
        显然,DFA是NFA的特例。实际上,对于每个NFAM,都存在一个DFAN,L(M)=L(N)。
        词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号,然后构造相应有限自动机的状态转换图,最后依据状态转换图编写词法分析器(程序)。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2023 All Rights Reserved
软考在线版权所有