THE GATEBOOK

Normalization Lectures

Consider the following statements

S1 : Define the language SUBCFG to be {(G1, G2): G1 and G2 are CFG's and L(G1) 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