question 5

Let ALL_DFA = { | A is a DFA and L(A) = sigma^* (where sigma is the alphabet of A)}. Show that ALL_DFA is decidable. Let SUB_DFA = { | A, B are DFAs, and L(A) L(B)}. Show that SUB_DFA is decidable. Let LEN_CFG = { | G is a CFG, k elementof Z^noneg, and L(G) Intersection sigma^k notequalto (where sigma is the alphabet of G)}. Show that LEN_CFG is decidable. Let INT_TM = {: M_1, M_2 are TMs and L(M_1) Intersection L(M_2) notequalto}. Show that INT_TM is undecidable, by reducing A_TM to it (showing that if you could decide INT_TM then you could decide A_TM). Let D = {: M is a TM that accepts epsilon}. Show that D is undecidable