Main Undecidable Problems
1. Equivalence problem:
•
Instance:
CFGs
G
1
,
G
2
;
Question:
L
(
G
1
)
=
L
(
G
2
)
?
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