Main Undecidable Problems
1. Equivalence problem:
• Instance: CFGs G1, G2;Question: L(G1) = L(G2)?
2. Ambiguity problem:
• Instance: G;         Question: Is G ambiguous?
Note:
It is mathematically proved that there exists no algorithm, which solve these problems in finite time.
31/31