2008年下半年计算机软件设计师考试考前秋点兵

　　供选择的答案：

　　(28)A.以1开头的二进制代码串组成的集合

　　B.以1结尾的二进制代码串组成的集合

　　C.包含偶数个0的二进制代码串组成的集合

　　D.包含奇数个0的二进制代码串组成的集合

　　(29)A.1*0(0|1)* B.((0|1*0)*1*)*

　　C.1*((0|1)0)* D.(1*(01*0)*)*

　　首先，我对状态图做一些说明。在状态转换图中，末端没有状态连接的“→”所指向的结点为初态结点，而终态用双环圈表示，显然，该题中q0既是初态又是终态，那么该DFA显然能识别空串，当处于q0时输入0便转换到q1，而当处于q1时输入0又回到q0，并且在q0或q1状态连续输入n≥0个1仍回到原状态，因此，该DFA识别的串是包含偶数个0的二进制代码串，即在偶数个0之间或前后可插入任意个1的串，如ε、00、010、10101、1011011、1001101101。

　　对于正规式，首先来了解几个符号的意思：“*”号的意思，在正规式中，它表示任意自我连接，比如，a*表示n≥0个a...，而(ab)*表示n≥0个ab相连： ababab...;“|”表示或;“●”表示连接，常省略，如a●b=ab。

　　如果某有穷自动机所能识别的字符串集跟某正规式对应的正规集相等，则称两者等价。将有穷自动机转M化为与其等价的正规式R的步骤为：

　　首先，在M的转换图上加进两个状态x和y，从x用标有ε的弧连接到M的所有初态结点，从M的所有终态结点用标有ε的弧连接到y，从而形成一个新的有穷自动机，记为M’，它只有一个初态x和一个终态y，显然L(M)=L(M’), L(M)表示M所能接受的字符串集。