Equivalence problem

from Wikipedia, the free encyclopedia

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.

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 .

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.

See also


  • 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 .