试题出自试卷《2006年下半年软件设计师考试基础知识真题（专业解析+参考答案）》

问题1选项
A.由符号a.b构成且包含偶数个a的串
B.由符号a.b构成且开头和结尾符号都为a的串
C.由符号a.b构成的任意串
D.由符号a.b构成且b的前后必须为a的串

问题2选项
A.(a∣b)*(aa)*
B.a(a∣b)*a
C.(a∣b)*
D.a(ba)*a

第1题:B

第2题: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”。