Peter Linz-Chapter: 12 -Exercise: 12.4
0 votes
0 votes
  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:


          * G2 is unrestricted

          * G2 is context free

          * G2 is regular?

in Theory of Computation


  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 Answer

0 votes
0 votes
  1. Suppose $G_{1}$ is CFG

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


  $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

1.0k points
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.