Hlavní nerozhodnutelné problémy
1. Problém ekvivalence:
• Instance: CFGs G1, G2;   Otázka: L(G1) = L(G2)?
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