Grand Test TOC Q17

0 votes

Consider the following statements

S1 : Define the language SUBCFG to be {(G1, G2): G1 and G2 are CFG's and L(G1) \subseteq L(G2)}. SUBCFG is not Turing decidable.

S2 : Define the language TRTM to be {M: M is a Turing machine and L(M) is Turing Recognizable }. TRTM is Turing decidable. 

Which of the above statement is/are CORRECT ?

A. Only S1

B. Only S2

C. Both S1 and S2

D. Neither S1 nor S2

asked Dec 10, 2019 in TOC by getgatebook (34,830 points)
reshown Dec 11, 2019 by getgatebook

1 Answer

0 votes
Best answer
Answer : C

S1 : Containment/inclusion problem (subset problem) for CFL's is Undecidable.

S2 : Apply rice's theorem. It is Trivial property so decidable.
answered Dec 11, 2019 by (7,500 points)
selected Dec 14, 2019 by getgatebook