软考中级
设有穷自动机的状态转换图如下图，该自动机识别的语言是(29)。A．∑={0，1)上的所有符号串的集合，但不包含空符号串B．空符号串集合C．∑={0，1)上的所有符号串的集合，包含空符号串D．空集合
题目
设有穷自动机的状态转换图如下图，该自动机识别的语言是(29)。
A．∑={0，1)上的所有符号串的集合，但不包含空符号串
B．空符号串集合
C．∑={0，1)上的所有符号串的集合，包含空符号串
D．空集合
参考答案和解析
解析：因为从有穷自动机的开始状态A出发，无法到达终止状态B，所以该有穷自动机不能接受任何符号串，即该有穷自动机识别的语言为空集合。
相似问题和答案
第1题：
在编译原理中，语言是
A．句子的集合
B．产生式的集合
C．符号串的集合
D．句型的集合
第2题：
设x是符号串，符号串的幂运算x0=（)。
A．1
B．x
C．Ɛ
D．空集
第3题：
3。给出正则表达式表示字母表{a,b}上的符号串，但符号串不能包含两个相邻的a,也不能包含两个相邻的b.
第4题：
4、文法 G 所描述的语言是（)的集合。
A．文法 G 的字母表 V 中所有符号组成的符号串
B．文法 G 的字母表 V 的闭包 V* 中的所有符号串
C．由文法的开始符号推出的所有符号串
D．由文法的开始符号推出的所有终结符号串
第5题：
● 设某语言的语法规则用上下文无关文法G=(N,T,P,S)表示，其中N是非终结符号的集合，T是终结符号的集合，P 是产生式集合，S是开始符号，令V=N∪T，那么符合该语言的句子是 （50） 。
（50）
A. 从S 出发推导的、仅包含T 中符号的符号串
B. 从N 中符号出发推导的、仅包含T 中符号的符号串
C. 从S 出发推导的、包含V 中符号的符号串
D. 从N 中符号出发推导的、包含V 中符号的符号串
第6题：
若将有限状态自动机(DFA)识别的0、1符号串看作二进制数，则(6)识别的是能被十进制数3整除的正整数，(7)是与该自动机等价的正规式。
A．
B．
C．
D．
解析：任何一个整数被3除后，余数或为0、或为1、或为2。因此，若将该DFA识别的0、 1串看作是二进制整数，则有以下结论：
▲ 0被3除，余数为0。
▲ 设能被3整除的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数仍然为0。若在x之后连接一个1所得的数为y，则y=2x+1，因此， y被3整除的余数将等于1。
▲ 设被3整除后余数为1的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数为2。若在x之后连接一个1所得的数为y，则y2x+l，且y被3整除的余数将等于0。 ‘
▲ 设被3整除后余数为2的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数为1。若在x之后连接一个1所得的数为y，则y=2x+l，且y被3整除的余数仍等于2。
综上，设被3除后的余数为0用qo(下标)表示、余数为1用q1(下标)表示、余数为2用q2(下标)表示，若将空串的值看作0，则下图所示的自动机识别的是能被3整除的整数，其正规式为(0* (1(01*0)*1)*)*。
若限定该自动机识别的0、1序列不能为空串，则相应自动机的状态转换图如下图所示。
第7题：
文法G所描述的语言是______的集合。
A.文法G的字符表V中所有符号组成的符号串
B.文法G的字符表V的闭包V*中的所有符号串
C.由文法的识别符号推出的所有符号串
D.由文法的识别符号推出的所有终结符号串
第8题：
设某语言的语法规则用上下文无关文法G=(N，T，P，s)表示，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，s是开始符号，令V=N∪T，那么符合该语言的句子是( )。
A．从s出发推导的、仅包含T中符号的符号串
B．从N中符号出发推导的、仅包含T中符号的符号串
C．从S出发推导的、包含V中符号的符号串
D．从N中符号出发推导的、包含V中符号的符号串
解析：一个文法的语言是该文法能产生的句子的集合。一个文法产生的句子是从文法开始符号出发推导出的所有终结符号串。
第9题：
A、句子
B、产生式
C、符号串
D、句型