正规式与有限自动机

1、正规式与有限制动机正规式与有限自动机正规式与有限自动机之间的转换1）有限自动机转换为正规式对于S上的NFAA/,可以构造一个S上的正规式/?,使得切。拓广状态转换图的概念，令每条弧可用一个正规式作标记。为S上的NFA Af构造相应的 正规式及，分为如下两步。（1）在M的状态转换图中加两个节点，一个x节点，一个y节点。从x节点到NFAM的 初始状态节点引一条弧并用e标记，从NFAM的所有终态节点到y节点引一条弧并用e标记。 形成一个与A/等价的MS AT只有一个初态jc和一个终态少。（2）按下面的方法逐步消去中除x和；的所有节点。在消除节点的过程中，用正规式来 标记弧，最后节点jc和；之间弧上的

2、标记就是所求的正规式。消除节点的规则如图2-12所示。2）正规式转换为有限自动机同样地，对于S上的每个正规式/?,可以构造一个S上的NFAAf,使得L（A0=Z（及）。（1）对于正规式i,可用图>13所示的拓广状态图表示。R o（1）通过对正规式/?进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是E上的一个字符或e,转换规则如图 2-14所示。最后所得的图即为一个NFAM,JC为初态节点，少为终态节点。显然，L（A0=I（及）。【试题 2-24】2011年 11月真题 48下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机识别的语言可用正规式（48）表示。 A

3、. (0|1)*01 B. 1*0*10*1 C. 1*(0)*01 D. 1*(0|10)*1*分析：在正规式中，符号 *表示重复若干次（包括 0次），符号 |表示“或”。在状态 A，可以输入 1或0，如果输入1还可以回到状态A，如果输入 0直接到达状态B；在状态 B，可以输入 0或1，如果输入 0则还回到状态 B，而输入 1，则进入到状态 C；在状态 C可以输入0或1，输入 0到达状态B，输入 1到达状态A，但由于 C是终态，自动机可识别的语言是由0、1构成的字符串的集合，但该集合必须以 01结果，因此选项 A正确。【答案：A】【试题 2-25】2011年 5月真题 15包含8个成员的开发

4、小组的沟通路径最多有（ 15）条。（15）A28 B32 C56 D64分析：需要协作沟通的人员的数量影响着开发成本，因为成本的主要组成部分是相互的沟通和交流，以及更正沟通不当所引起的不良结果。人与人之间必需通过沟通来解决各自承担任务之间的接口问题，如果项目有n个工作人员，则有n×（n -1）/ 2个相互沟通的路径。很明显，包含8个成员的开发小组的沟通路径最多有28条。这其实是一道简单的图论问题，相当于求包含 8个顶点的无向图中最多有多少条边。【答案：A】【试题 2-26】2011年 5月真题 49下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机可识别（ 49）。

5、60;（49）A0000 B1111 C0101 D1010 分析：有限自动机可识别的字符串，是指从有限自动机的初态出发，存在一条到达终态的路径，其上的标记所构成的字符串。对于“ 0000”，其识别路径是状态 A状态B状态B状态B状态B，没有到达态。对于“1111”，其识别路径是状态A状态A状态A状态A状态A，没有到达态。对于“0101”，其识别路径是状态A状态B状态C状态B状态C，状态C为终态，可以识别。对于“1010”，其识别路径是状态A状态A状态B状态C状态B，经过了终态，但没有以终态结束。【答案：C】【试题 2-27】2010年 11月真题 22下图所示的有限自动机中，0是初始状态，3

6、是终止状态，该自动机可以识别（22）。 （22）Aabab Baaaa Cbbbb Dabba分析：从初始状态到终止状态有多条路径。在状态 0输入a到达状态2，在状态 2可输入a或b，输入 a到达状态1，输入 b到达状态3，状态3下输入a还回到状态3；在状态 1可输入a或b，输入 a到达状态3，输入b到达状态2。【答案：B】【试题 2-28】2010年 11月真题 48下图所示为两个有限自动机Ml和M2 (A是初态、C是终态），（48）。 CM1是确定的有限自动机，M2是不确定的有限自动机DM1是不确定的有限自动机，M2是确定的有限自动机分析：确定有限自动机对每一个可能的输

7、入只有一个状态的转移。非确定有限自动机对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。有限自动机 M1在状态A时，输入0可以回到状态A，也可以到达状态 B，可见 M1是不确定的。有限自动机 M2的每个状态下的输入都只有一个转移状态。【答案：D】考点 3 文法分析（4）【试题 2-29】2010年 5月真题 21逻辑表达式“abc(bx0)”的后缀式为（21）。（其中、分别表示逻辑与、逻辑或，表示关系运算大于，对逻辑表达式进行短路求值）（21）Aabcbx0 Babcbx0>Cabcbx>0 Dabcbx0> 分析：后缀式把运算符写在运算对

8、象后面。“逻辑与运算”的优先级高于“逻辑或运算”。对于逻辑表达式“abc(bx>0)”，从运算符的优先级方面考虑，需先对“ab”求值，然后对“c(bx>0)”求值，最后进行“”运算，因此后缀式为“abcbx0> ”。【答案：D】【试题 2-30】2010年 5月真题 50对于正规式0*(10*1)*0*，其正规集中字符串的特点是（50）。（50）A开头和结尾必须是0 B1必须出现偶数次C0不能连续出现 D1不能连续出现分析：闭包运算符“ *”将其运算对象进行若干次连接，因此 0*表示若干个0构成的串，而 (10*1)*则表示偶数个1构成的串。【答案：B】【试题 2-31】20

9、09年 11月真题 50由某上下文无关文法MS推导出某句子的分析树如图所示，则错误叙述的是（ 50）。（50）A该文法推导出的句子必须以“a”开头 Bacabcbdcc是该文法推导出的一个句子C“S aAcB”是该文法的一个产生式 Da、b、c、d属于该文法的终结符号集分 析：上图是某上下文无关文法MS推导出某句子的分析树，看图只要稍作推导就可推出 “acabcbdcc”是该文法推导出的一个句子；看该分析树的第一层分枝即可知 “S aAcB”是该文法的一个产生式；而 a、b、 c、d因为在图中是分析树的叶子，都是该文法的终结符号；右边的B分枝下有S Bd，B ，所以该文法推导出的句子不一定是“

10、a”开头，因此答案A是不正确的。【答案：A】【试题 2-32】2009年 5月真题 48下图所示有限自动机的特点是（48）。 （48）A识别的0、1串是以0开头且以1结尾 B识别的0、1串中1的数目为偶数C识别的0、1串中0后面必须是1 D识别的0、1串中1不能连续出现分 析：由图可知，从初始态q0输入0仍然到q0或者输入1到达终态q1，从q1还可以输入0重新到达初始态 q0，所以这个有限自动机识别的 0、1串不一定是以0开头的，1的数目的奇偶性也没办法确定，0后面也可以是 0，所以A、B、C都是错误的。从q0输入1到达终态q1后，或者串结束，或者输入0再到q0，所以这个串中的1不会

11、连续出现，D是正确的。【答案：D】【试题 2-33】2009年 5月真题 49由a、b构造且仅包含偶数个a的串的集合用正规式表示为（ 49）。（49）A(aa)b* B(b (aba)* C(a (ba)b) D(a|b) (aa)*分 析：本题主要考察考生对闭包概念的理解。【答案：B】*：指包括空串在内的上所有字符串的集合。关键在于*可取空串。理解了这个概念就不难看出答案B是正确的。【试题 2-34】2009年 5月真题 50程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法=(N，T，P，S)，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号。

12、令集合V= N T，那么 G所描述的语言是（50）的集合。A从S出发推导出的包含V中所有符号的串 B从S出发推导出的仅包含T中符号的串CN中所有符号组成的串 DT中所有符号组成的串分 析：若VNV，根据上下文无关文法的特性，V总可以被字符串NV自由地替换。但当V= NT时，由于非终结符的不唯一性，要构成等式成立，必须要NT中的符号串收缩为终结符，即都是T的集合。所以上下文无关文法G描述的语言是从S出发推导出的仅包含T中符号的串的集合。【答案：B】【试题 2-35】2008年 12月真题 48给定文法GS及其非终结符A，FIRST(A)定义为：从 A出发能推导出的终结符号的集合（ S是文法的起始

13、符号，为非终结符）。对于文法GS：SL | aLL, S| S其中，GS包含的四个终结符号分别为：a , 则FIRST(S)的成员包括（ 48）。（48）Aa Ba、 Ca、和 Da、和，分 析：由SL | a得SL和Sa，所以FIRST(S)=，a。【答案：B】【试题 2-36】2008年 12月真题 50设某上下文无关文法如下：S11 | 1001 | S0 |SS，则该文法所产生的所有二进制字符串都具有的特点是（50）。（50）A能被3整除  B0、1出现的次数相等C0和1的出现次数都为偶数 D能被2整除分  析：本题考查上下文无关文法产生的字符串集合。【答案：A】B

14、选项：由S11，B显然不正确。C选项：由S11和S0S有S011，C不正确。D选项：由S11，二进制11为十进制3，不能被2整除，D不正确。【试题 2-37】2008年 5月真题 21已知某文法GS:S0S0 S1，从S推导出的符号串可用（21） (n0) 描述。分 析：推导树为：可以看出S 1就结束了，所以不可能产生1n（C、D被排除）。也不可能产生010010010这样的式子，还是因为S 1就结束了，不会有多个1这样的式子的。【答案：B】【试题 2-38】2008年 5月真题 48有限自动机（ FA）可用于识别高级语言源程序中的记号（单词），FA可分为确定的有限自动机（ DFA）和不确定的有限自动机（NFA）。若某DFA D与某NFA M等价，则（ 48）。（48）ADFA D与NFA M的状态数一定相等BDFA D与NFA M可识别的记号相同CNFA M能识别的正规集是DFA D所识别正规集的真子集DDFA D能识别的正规集是NFA M所识别正规集的真子集分 析：本题考查DFA和NFA的相关知识。【答案：B】有限自动机的确定化：对于任一个NFA M，都可以构造其对应的DFA M'，使这两个自动机接受相同的字符串集合：L(M )