Let L={ | G is a CFG, M is a TM, and L(M) is a subset of L(G)}. Classify L as (a) decidable (b) Turing-recognizable
Posted: Fri May 20, 2022 5:45 pm
Let L={<G,M> | G is a CFG, M is a TM, and L(M) is a subset
of L(G)}. Classify L as (a) decidable (b) Turing-recognizable but
no co-Turing-recognizable (c) co-Turing -recognizable but not
Turing- recognizable, (d) neither Turing-recognizable nor co-Turing
recognizable. Justify your answer
of L(G)}. Classify L as (a) decidable (b) Turing-recognizable but
no co-Turing-recognizable (c) co-Turing -recognizable but not
Turing- recognizable, (d) neither Turing-recognizable nor co-Turing
recognizable. Justify your answer