软考初级
●若正规式为“(1︱01)*0”，则该正规式描述了(28)。(28)A．长度为奇数且仅由字符0和l构成的串B．长度为偶数且仅由字符0和l构成的串C．以0结尾、0不能连续出现且仅由字符0和l构成的串D．以1开始以0结尾且仅由字符0和1构成的串
题目
●若正规式为“(1︱01)*0”，则该正规式描述了(28)。
(28)A．长度为奇数且仅由字符0和l构成的串
B．长度为偶数且仅由字符0和l构成的串
C．以0结尾、0不能连续出现且仅由字符0和l构成的串
D．以1开始以0结尾且仅由字符0和1构成的串
相似问题和答案
第1题：
● 正则表达式 1*(0|01)*表示的集合元素的特点是（48） 。
（48）
A. 长度为奇数的 0、1 串
B. 开始和结尾字符必须为 1 的 0、1 串
C. 串的长度为偶数的 0、1 串
D. 不包含子串 011 的 0、1 串
第2题：
某一确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|19，则以下字符串中，不能被该DFA接受的是(28)，与该DFA等价的正规式是(29)。(其中，ε表示空字符)
①3857
②1.2E+5
③-123．
④.576E10
A．①、②、③
B．①、②、④
C．②、③、④
D．①、②、③、④
解析：有限自动机也称为有穷状态自动机，是一种数学机器模型，基本形式有非确定有限自动机(NFA)和确定的有限自动机(DFA)，并且每一个NFA都有与其等价的DFA。有穷状态自动机的物理模型如下图所示。
一个DFA可以用状态转换图直观的方式。状态转换图是一种有向图。DFA中的每个状态对应转换图中的一个节点，从外部引入弧的节点表示开始节点，双圈节点表示终态；DFA中的每个状态转换对应图中的一条有向弧，若转换关系为/(A，a)=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。
有穷状态自动机识别字符串的过程为：初始时，机器处于起始状态(题图中节点0表示初始状态)。读取一个输入符号，并进行相应的状态转移，直到输入串结束或找不到
相应的状态转移时为止。
根据题目终给定的自动机，识别3857、1.2E+5、-123.、.576E10的过程分别如下。
分析题中给定的有穷状态自动机，可知该自动机识别以下形式的数值：带小数部分的十进制表示形式和以尾数、指数表示的数值形式。其中，从初态0到达终态5所识别的是带小数点的以十进制数值表示形式的字符串，小数点后可以没有数字，也可以有若干个数字，而小数点之前的整数部分可以不带符号，也可以带负号，其正规式为“(-d|d) d*.d，”。当数值的表示含有指数部分时，指数部分是不带符号(表示正数)或带负号的整数形式，因此该部分的正规式为“E(-d|d)d*”。
第3题：
● 对于正规式0*(10*1)*0*，其正规集中字符串的特点是 （50） 。
（50）
A. 开头和结尾必须是0
B. 1必须出现偶数次
C. 0不能连续出现
D. 1不能连续出现
第4题：
若字符串s的长度为n(n＞1)且其中的字符互不相同，则s的长度为2的子串有______个。
A．n
B．n-1
C．n-2
D．2
A．
B．
C．
D．
第5题：
● 若字符串s 的长度为 n（n >1）且其中的字符互不相同，则 s 的长度为 2 的子串有 （35） 个。
（35）
A. n
B. n-1
C. n-2
D. 2
第6题：
下图是一有限自动机的状态转换图，该自动机所识别语言的特点是(45)，等价的正规式为(46)。
A．由符号a、b构成且包含偶数个a的串
B．由符号a、b构成且开头和结尾符号都为a的串
C．由符号a、b构成的任意串
D．由符号a、b构成且b的前后必须为a的串
解析：本题考查有限自动机的基本运算。在有限自动机的状态转换图中，每一个结点代表一个状态，其中双圈是终态结点。对于字符串ω，若存在一条从初态结点到某一终止状态结点的路径，且这条路径上所有弧的标记符连接成的字符串等于ω，则称①可由DFA M识别(接收或读出)。若一个 DFA M的初态结点同时又是终态结点，则空字ε可由该DFA识别(或接收)。DFA M所能识别的语言L(M)={ω|ω①是从M的初态到终态的路径上的弧上标记所形成的串}。分析题中给出的自动机：从初态0出发，识别一个符号a后进入状态1，在状态1可识别出任意个a或(和)任意个b，再识别出一个a而到达终态2。显然，该自动机识别的语言特点是“由a开头由a结尾，期间的a、b任意排列”。用正规式表示为“a(a|b)*a”。
第7题：
由a、b构造且仅包含偶数个a的串的集合用正规式表示为( )。
A．(a*a)*b*
B．(b*(ab*a)*)*
C．(a*(ba*)*b)*
D．(a I b)*(aa)*
解析：在正规式中，符号*表示重复若干次(包括O次)，因此正规式“(a*a)*b*”中的表达式“(a+a)*”不能保证有偶数个a。同理，“(a*(ba*)*b)*”和“(a I b)*(aa)*”中对a的个数也没有限制，而在“(ab * a)*”中可以确保a的出现为偶数个。
第8题：
表示“以字符a开头且仅由字符a、b构成的所有字符串”的正规式为（）。
A.a*b*
B.（a|b）*a
C.a（a|b）*
D.（ab）*
第9题：
A.0开头的串
B.1开头的串
C.有一个0和一个1的串
D.由0、1组成的任意串
第10题：
图7-17是一有穷自动机的状态转换图，该自动机所识别语言的特点是(1)，等价的正规式为(2)。
A．由符号a、b构成且包含偶数个a的串
B．由符号a、b构成且开头和结尾符号都为a的串
C．由符号a、b构成的任意串
D．由符号a、b构成且b的前后必须为a的串