可判定性练习(共5页).doc

精选优质文档-倾情为你奉上第5章、可判定性习题解答 练习5.1 对于下图所示的DFA M，回答下列问题，并说明理由。1010，10a. ADFA？是，M接受0100。b. ADFA？否，M不接受011。c. ADFA？否，不是ADFA的有效输入编码。d. AREX？是，DFA和正则表达式等价。e. EDFA？否，M接受串0100。f. EQDFA？是，L(M) = L(M)5.2考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。解：设EQD-R=|A是DFA，B是正则表达式，L(A)=L(B)。构造如下TM F，F=“对于输入 , A是DFA，B是正则表达式，1) 将正则表达式B转化为等价的DFA C。2) 判定EQDFA（EQDFA可判定）。3) 若接受，则接受；若拒绝，则拒绝。”F判定EQ