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_CFG

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

Useless and Unreachable variables

A variable is useless if it generates no string consisting entirely of terminals. All non-useful variables are useless

A variable is unreachable if it can never be generated (starting with ).

High-Level Description

On input

1. Check whether indeed encodes a CFG. If not, reject.
2. Delete all useless and unreachable variables.
3. Is still remains accept. Else, reject.

Since all these steps take a finite amount of time, it is guaranteed that the machine halts and decides.

Any PDA can be converted to an equivalent CFG. Thus, the following language is also decidable since it reduces to .

E_PDA