Problém ekvivalence - Equivalence problem
v teoretická informatika a teorie formálního jazyka, problém ekvivalence je otázka určení, vzhledem ke dvěma reprezentacím formálních jazyků, zda označují stejný formální jazyk.
Složitost a rozhodnost rozhodovací problém záleží na typu uvažované reprezentace. Například v případě konečné automaty, rovnocennost je rozhodnutelná a problém je PSPACE - kompletní, zatímco to je nerozhodnutelný pro pushdown automaty, bezkontextové gramatiky, atd.[1]
Reference
- ^ J. E. Hopcroft a J. D. Ullman. Úvod do teorie automatů, jazyků a výpočtu, první vydání, 1979.
 | Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |