Decidable Languages : ADFA, ANFA, AREX, ARG

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.

A_DFA

$\begin{equation*} A_{DFA} = \{ <D, w>: D \text{ is a DFA that accepts }w \} \end{equation*}$

There exists a TM that decides the above language. Given the string encoding of a DFA $D$ and some string $w$ , a TM can decide whether $D$ accepts $w$ .

High-Level Description

On input $<D, w>$

Check whether $<D>$ indeed encodes a DFA. If not, reject.
Record that $D$ is in the start state $q_0$ , reading first symbol of $w$ .
Based on the current state of $D$ and current symbol of $w$ , compute the new state. Change the current state to the new state and to the next symbol of $w$ . Repeat this step until all of $w$ is read.
If $D$ is in a final state, accept. Else reject.

Steps 2 and 3 can be summarized as simulating the DFA $D$ on the input $w$ . Since all these steps take a finite amount of time, it is guaranteed that the machine halts and decides.

A_NFA

$\begin{equation*} A_{NFA} = \{ <N, w>: N \text{ is a NFA that accepts }w \} \end{equation*}$

High-Level Description

On input $<N, w>$

Check whether $<N>$ indeed encodes a NFA. If not, reject.
Convert the NFA $N$ to an equivalent DFA $D$ using the power-set method.
Run $A_{DFA}$ on $<D, w>$ .

Thus, $A_{NFA}$ is decidable because it can be reduced to $A_{DFA}$ .

A_REX

$\begin{equation*} A_{REX} = \{ <R, w>: R \text{ is a regular expression and }w \in L(R) \} \end{equation*}$

High-Level Description

On input $<R, w>$

Check whether $<R>$ indeed encodes a regular expression. If not, reject.
Convert the regular expression $R$ to an equivalent NFA $N$ using the GNFA method.
Run $A_{NFA}$ on $<N, w>$ .