下图是一有限自动机的状态转换图,该自动机所识别语言的特点是(45),等价的正规式为(46)。A.由符号a

Question

下图是一有限自动机的状态转换图，该自动机所识别语言的特点是(45)，等价的正规式为(46)。

A．由符号a、b构成且包含偶数个a的串

B．由符号a、b构成且开头和结尾符号都为a的串

C．由符号a、b构成的任意串

D．由符号a、b构成且b的前后必须为a的串

Answer 1

正确答案：B
解析：本题考查有限自动机的基本运算。在有限自动机的状态转换图中，每一个结点代表一个状态，其中双圈是终态结点。对于字符串ω，若存在一条从初态结点到某一终止状态结点的路径，且这条路径上所有弧的标记符连接成的字符串等于ω，则称①可由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”。