Als Äquivalenzproblem bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob zwei formale Sprachen und äquivalent sind, also .
Für (vgl. Chomsky-Hierarchie) ist das Äquivalenzproblem wegen der Entscheidbarkeit des Leerheitsproblems und der Abschlusseigenschaften entscheidbar, da genau dann, wenn .
