Decidable Languages : EDFA, ENFA, EREX, ERG

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.

E_DFA

$\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>$

Check whether $<D>$ indeed encodes a DFA. If not, reject.
Construct the directed graph described by the transition function of $D$ .
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}$ .

E_NFA

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

E_REX

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

E_RG

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

Decidable Languages : E_DFA, E_NFA, E_REX, E_RG

E_DFA

High-Level Description

E_NFA

E_REX

E_RG

Leave a Reply Cancel reply