Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language.
Consider the following problems:
(A) Is L(G1) = L(G2)?
(B) Is L(G2) ≤ L(G1)?
(C) Is L(G1) = R?
Which of the problems are undecidable ?
Choose the correct answer from the options given below:
Solution
The correct answer is option 4.
Key Points
| S.NO |
|
FA
Regular
|
PDA
DCFL
|
PDA
CFL
|
LBA
CSL
|
Recursive
HTM
|
REL
TM
|
| 1 |
Membership WεL
|
D |
D |
D |
D |
D |
UD |
| 2 |
Finiteness L= finite |
D |
D |
D |
UD |
UD |
UD |
| 3 |
Equivalence L1=L2 |
D |
D |
UD |
UD |
UD |
UD |
| 4 |
Is L1⊆ L2 Subset Checking |
D |
UD |
UD |
UD |
UD |
UD |
| 5 |
Emptiness L1=Φ |
D |
D |
D |
UD |
UD |
UD |
| 6 |
Disjoint Operator is L1∩L2=Φ |
D |
UD |
UD |
UD |
UD |
UD |
| 7 |
Is L= Σ* Totality |
D |
UD |
UD |
UD |
UD |
UD |
| 8 |
Is L regular language |
D |
D |
UD |
UD |
UD |
UD |
- D =decidable
- UD=undecidable
|
According to the above table, rows 3,4, and 8 it's undecidable.
∴ Hence the correct answer is (A), (B) and (C).