Peter Linz-Chapter: 12 -Exercise: 12.4

Question

1. Let G1 be a context free grammar and G2 a regular grammar. Is the problem decidable?

         $L(G1) \cap L(G2)= \phi$

2. Let L1 be a regular language and G a context free grammar. Is the problem decidable?

         $L1\subseteq L(G)$

      3. Let G1 and G2 be grammars with G1 regular. Is the problem decidable when:

          $L(G1)=L(G2)$

          * G2 is unrestricted

          * G2 is context free

          * G2 is regular?

Comments

1. undecidable
2. undecidable

@Shaik @Satbir, can u tell me what is unrestricted grammar mean?

---

For 1. and 2. Please provide a little explanation.

And unrestricted grammar means =Recursively enumerable grammar

Answer 1

1. Suppose $G_{1}$ is CFG

 and $G_{2}$ is the regular grammar. So, we can say it is also a CFG.

Now, 

  $L(G1) \cap L(G2)= \phi$

We know for CFG it will be undecidable. Hence , here too, we can say it will be undecidable 

---

2. Same as above.

$L1\subseteq L(G)$ also undecidable for CFG

---

3.  When $G_{1}$ is regular

• $G_{2}$ is Recursive Enumerable $L(G1)=L(G2)$ will be undecidable
• $G_{2}$ is CFG $L(G1)=L(G2)$ will be undecidable
• $G_{2}$ is Regular $L(G1)=L(G2)$ will be decidable

https://gatecse.in/grammar-decidable-and-undecidable-problems/