Question: PLEASE DO THE QUESTION 3 !! Let ALL_DFA = {(A) | A is a DFA and L(A) = sigma* (where sigma is the alphabet
Let ALL_DFA = {(A) | 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) | A, B are DFAs, and L(A) L(B)}. Show that SUB_DFA is decidable. Let LEN_CFG = {(G, k) | G is a CFG, k elementof Z^noneg and L(G) sigma^k notequalto 0 (where sigma is the alphabet of G)}. Show that LEN_CFG is decidable. Let INT_TM = {(M_1, M_2): M_1, M_2 are TMs and L(M_1) L(M_2) notequalto 0}. 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): M is a TM that accepts elementof}. Show that D is undecidable
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
