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

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

1. 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?

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

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/

by
1.0k points