Decidable Languages : EDFA, ENFA, EREX, ERG

posted in Theoretical Computer Science on by

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.

EDFA

      \begin{equation*} E_{DFA} = \{ <D>: D \text{ is a DFA with } L(D) = \emptyset \} \end{equation*}

There exists a TM that decides the above language. Given the string encoding of a DFA D, a TM can decide whether the language of D is empty.

High-Level Description

On input <D>

  1. Check whether <D> indeed encodes a DFA. If not, reject.
  2. Construct the directed graph described by the transition function of D.
  3. Perform a Breadth-First Search starting at the start state q_0. If any final state is encountered, reject. If no final states are encountered, accept.

The idea behind this approach is this: A DFA that has a path from the start to the final state must have an accepting computation – the path itself.

Since all these steps take a finite amount of time, it is guaranteed that the machine halts and decides.

The following languages are also decidable because they can all be reduced to E_{DFA}.

ENFA

      \begin{equation*} E_{NFA} = \{ <N>: N \text{ is an NFA with } L(M) = \emptyset \} \end{equation*}

EREX

      \begin{equation*} E_{REX} = \{ <R>: R \text{ is a regular expression with } L(R) = \emptyset \} \end{equation*}

ERG

      \begin{equation*} E_{RG} = \{ <G>: G \text{ is a regular grammar with } L(G) = \emptyset \} \end{equation*}

Leave a Reply

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