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}

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

## High-Level Description

On input

- Check whether indeed encodes a DFA. If not,
*reject*. - Construct the directed graph described by the transition function of .
- Perform a Breadth-First Search starting at the start state . 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 .