toc grammer

Question

Consider two grammars G₁ and G₂ that describe the languages L(G₁) and L(G₂) respectively over some common alphabet Σ, and let f denote the empty language. The problem “Is L(G₁) ∩ L(G₂) = f ?” is decidable for which of the following cases?

I. Both G₁ and G₂ are regular grammars.

II. Both G₁ and G₂ are context free grammars.

III. G₁ is a regular grammar and G₂ is a context free grammar, or vice-versa.

Comments

Only 1?

Answer 1

The problem is intersection empty problem and intersection empty problem is decidable in case of both the languages are regular 

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

Answer 2

I. Both G₁ and G₂ are regular grammars.  L(G₁) ∩ L(G₂)  = regular. Can decide whether regular is empty. => Decidable

II. Both G₁ and G₂ are context free grammars. L(G₁) ∩ L(G₂)  = not closed. Above CFG, emptiness is undecidable. => Undecidable

III. G₁ is a regular grammar and G₂ is a context free grammar. L(G₁) ∩ L(G₂) = context-free. Can decide whether CFG is empty. => Decidable.