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.

ADFA

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

  1. Check whether <D> indeed encodes a DFA. If not, reject.
  2. Record that D is in the start state q_0, reading first symbol of w.
  3. 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.
  4. 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.

ANFA

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

High-Level Description

On input <N, w>

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

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

AREX

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

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

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

ARG

    \begin{equation*} A_{RG} = \{ <G, w>: G \text{ is a regular grammar and }w \in L(G) \} \end{equation*}

High-Level Description

On input <G, w>

  1. Check whether <G> indeed encodes a regular grammar. If not, reject.
  2. Convert the regular grammar G to an equivalent NFA N.
  3. Run A_{NFA} on <N, w>.

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

Leave a Reply

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