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}

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

## High-Level Description

On input

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

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

## A_{NFA}

## High-Level Description

On input

- Check whether indeed encodes a NFA. If not,
*reject*. - Convert the NFA to an equivalent DFA using the power-set method.
- Run on .

Thus, is decidable because it can be *reduced* to .

## A_{REX}

## High-Level Description

On input

- Check whether indeed encodes a regular expression. If not,
*reject*. - Convert the regular expression to an equivalent NFA using the GNFA method.
- Run on .

Thus, is decidable because it can be *reduced* to .

## A_{RG}

## High-Level Description

On input

- Check whether indeed encodes a regular grammar. If not,
*reject*. - Convert the regular grammar to an equivalent NFA .
- Run on .

Thus, is decidable because it can be *reduced* to .