Decidable Language : EQDFA

A language is decidable if there is a Turing Machine that halts and accepts strings that belong to the language, and halts and rejects strings that do not belong to the language.


    \begin{equation*} EQ_{DFA} = \{ <D_1, D_2>: D_1 \text{ and } D_2 \text{ are DFAs with } L(D_1) = L(D_2) \} \end{equation*}

There exists a TM that decides the above language. Given the string encoding of two DFAs D_1 and D_2, a TM can decide whether the languages of the two DFAs are the same.

High-Level Description

On input <D_1, D_2>

  1. Check whether <D_1> and <D_2> indeed encode a DFA. If not, reject.
  2. Construct a DFA, D, for (L(D_1) \cup L(D_2)) \setminus (L(D_1) \cap L(D_2))
  3. Run E_{DFA} on <D>.

The idea behind this approach is this: if two DFAs have the same language their union and intersection will be the same. Thus, (L(D_1) \cup L(D_2)) \setminus (L(D_1) \cap L(D_2)) = \emptyset.

This extends to NFAs and regular expressions as well. Basically, the equivalence of regular languages is decidable as the problem can be reduced to EQ_{DFA}.

Leave a Reply

Your email address will not be published. Required fields are marked *