En informática teórica y teoría del lenguaje formal , el problema de equivalencia es la cuestión de determinar, dadas dos representaciones de lenguajes formales, si denotan el mismo lenguaje formal.
La complejidad y decidibilidad de este problema de decisión dependen del tipo de representación bajo consideración.
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 deterministas de tipo pushdown , la equivalencia es decidible; Géraud Sénizergues ganó el Premio Gödel por este resultado. Posteriormente, se demostró que el problema se encontraba en TOWER, la clase de complejidad no elemental más pequeña . [1]
Se convierte en un problema indecidible para los autómatas pushdown o cualquier máquina que pueda decidir lenguajes libres de contexto o lenguajes más potentes. [2]