Problém ekvivalence jazyků

Problém ekvivalence jazyků je v teoretické informatice a v teorii formálních jazyků problém rozhodnout, zda dané dvě reprezentace formálních jazyků generují stejný jazyk.

U jazyků zadaných konečným automatem je problém ekvivalence rozhodnutelný, ale je výpočetně velmi náročný, protože je PSPACE-úplný. V případě složitějších tříd jazyků, jako jsou jazyky generované zásobníkovým automatem nebo bezkontextovou gramatikou je problém ekvivalence algoritmicky nerozhodnutelný.

Odkazy

Reference

Kategorie:Formální jazyky Kategorie:Algoritmicky neřešitelné úlohy Ekvivalence jazyků