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ů