THE GATEBOOK

Normalization Lectures

S1: If X is any CFL and Y is any regular language, X ∩ Y must be regular.

S2 : If X and Y are each CFL's and neither X nor Y is regular, then must be a CFL and X ∪ Y must not be regular.

Which of the above statement is/are CORRECT ?

A. Only S1

B. Only S2

C. Both S1 and S2

D. Neither S1 nor S2

Answer : D

S1 : Take

S2 : Take