in Theory of Computation edited by
0 votes
0 votes

$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case,  $L(G1) \cap L(G2) = \phi$ is a/an:

  1. Decidable problem
  2. Undecidable problem
  3. Cannot ascertain
  4. None
in Theory of Computation edited by

1 Answer

1 vote
1 vote
Best answer

G1: Regular Grammar and G2:Regular Grammar
Suppose L1= L(G1)   and L2 = L(G2)

Take another language L such that
L= (L1 - L2) U(L2 - L1)    //EXOR of Both
L= (L1∩ L2c) U (L2∩L1c)

L1 and L2 are regular languages hence closed under complement and intersection
L=Regular U Regular = Regular

And Regular is closed under emptiness property, so if L is empty language it means both have disjoint property, so overall problem is Decidable which makes option (A) true.

selected by

Related questions