Problema de equivalencia

En la informática teórica y la teoría de lenguajes formales , el problema de equivalencia consiste en determinar, dadas dos representaciones de lenguajes formales, si denotan el mismo lenguaje formal.

La complejidad y la posibilidad de decisión de este problema dependen del tipo de representación que se esté considerando.

Por ejemplo, en el caso de los autómatas de estados finitos , la equivalencia es decidible y el problema es PSPACE-completo . Además, en el caso de los autómatas de pila deterministas , la equivalencia es decidible; Géraud Sénizergues ganó el Premio Gödel por este resultado. Posteriormente, se demostró que el problema pertenece a TOWER, la clase de complejidad no elemental más baja . ^{[ 1 ]}

Se convierte en un problema indecidible para los autómatas de pila o cualquier máquina que pueda decidir lenguajes libres de contexto o lenguajes más potentes. ^{[ 2 ]}