Register

Test by Bikram | Theory of Computation | Test 1 | Question: 29

• edited by
344 views
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
• edited by
User Avatar

1 Answer

Best answer
1 votes
1 votes

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
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1.4k
views
2 answers
6 votes
Bikram asked Nov 26, 2016
1,396 views
Test by Bikram | Theory of Computation | Test 1 | Question: 30
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decidableNot even semi-decidableIndeterminable
User Avatar
252
views
1 answers
0 votes
Bikram asked Nov 26, 2016
252 views
Test by Bikram | Theory of Computation | Test 1 | Question: 28
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
User Avatar
244
views
1 answers
0 votes
Bikram asked Nov 26, 2016
244 views
Test by Bikram | Theory of Computation | Test 1 | Question: 27
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is CORRECT?$S \subset T$T \subset S$S = T$S \cap T = \emptyset$
User Avatar
759
views
1 answers
1 votes
Bikram asked Nov 26, 2016
759 views
Test by Bikram | Theory of Computation | Test 1 | Question: 26
$L1$ and $L2$ are regular languages. $L3$ is CFL and $L4$ is a recursive enumerable language. $L5$ is the reversal of $L4$ ... input alphabet, then $L6$ is a:Regular LanguageCFLRecursive Enumerable LanguageNon Recursive Enumerable Language
User Avatar
Link Copied!