Hlavní nerozhodnutelné problémy
1.
Problém ekvivalence
:
•
Instance:
CFGs
G
1
,
G
2
;
Otázka:
L
(
G
1
)
=
L
(
G
2
)
?
2.
Problém jednoznačnosti
:
•
Instance:
G
;
Otázka:
Je
G
jednoznačná
?
Poznámka
:
Je matematicky dokázáno, že neexistují
žádné algoritmy, které by tyto problémy
vyřešily v konečném čase.
31
/31