Äquivalenzproblem

Als Äquivalenzproblem bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob zwei formale Sprachen $L 1$ und $L 2$ äquivalent sind, also $L 1 = L 2$ .

Für $\mathcal{L}_3$ (vgl. Chomsky-Hierarchie) ist das Äquivalenzproblem wegen der Entscheidbarkeit des Leerheitsproblems und der Abschlusseigenschaften entscheidbar, da $L 1 = L 2$ genau dann, wenn $( L_1 \cap \bar{L_2}) \cup (L_2 \cap \bar{L_1} ) = \empty$ .