Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)

Question

Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.

Answer 1

Since because language L1 is regular,

And every regular language is context free language so using L1 we would be able to construct equivalent CFG.

Then the main problem will become whether the language generated by one context free grammar is a subset of language generated by another context free grammar, which is Undecidable.