Equivalence problem

As equivalence problem is known in theoretical computer science the problem of deciding whether two formal definitions of two languages and are equivalent, so valid. ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}=L_{2}}$

The languages ​​can be defined by grammars, automata or completely differently.

The equivalence problem is decidable for regular grammars and deterministic context-free grammars , for non- deterministic context-free grammars it is undecidable. Obviously it makes sense to ask about the complexity of the equivalence problem if the problem is decidable. In this case this complexity can depend to a large extent on the given way in which the language is defined.

For regular languages the equivalence problem is decidable because of the decidability of the emptiness problem and the closure properties, since if and only if . ${\displaystyle L_{1}=L_{2}}$ ${\displaystyle (L_{1}\cap {\overline {L_{2}}})\cup (L_{2}\cap {\overline {L_{1}}})=\emptyset }$

If the languages and even in the form of DEA before, it can be the equivalent problem also decide by both DEA in each case the minimum machine forms and then this on isomorphism checked. If this is the case, the two languages and are also equivalent. ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$

See also

• Decidability
• Word problem
• Program equivalence
• Cutting problem
• Emptiness problem

literature

• Marco Almeida, Nelma Moreira and Rogério Reis: Testing the Equivalence of Regular Languages . In: 11th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009) EPTCS 3 . 2009, p. 47-57 , doi : 10.4204 / EPTCS.3.4 , arxiv : 0907.5058 .