# Turning Machine - Decidable Language

A **Turning Machine** which halts and never goes to the infinite loop is called **Deciders**. They always halt and decide whether to accept or reject the input. It always halt in accept or reject states.

A language of Turning Machine **L(M)**, is called **decidable** if there is a Turning machine **M**, which decides a language **L** and **M** halts on every input, such that -

##### L(M) = L

A decider of a language is the one that decides the language. It is also called **Recursive Language**. So, the decidable language always solves the decision problems.

## Decidable Problem

These are some decidable problems-

**Problem1:** There is a DFA **M** and an input string **w** decide if, **M** accepts **w**. The formal definition of this is written as-

##### A_{DFA} - {(M,w) | M is DFA and w ∈ L(M)}

Here, **M** simulates on **w** and returns "**Yes**", if M reaches a final state. If it does not, reject. So, this is decidable.

A turning machine decides language **L**, if it recognises the language and halt on every input.

**Problem2:** There is an NFA **N** that accepts input string **w**.

##### A_{NFA} - {N,w}

When we convert NFA **N** to DFA **D** and run the Turning machine **M** for **A _{DFA}** on input

**(D,w)**.

**M**simulates on

**w**and if

**M**reaches a final state, it accepts. If it does not, it rejects. So, this is decidable.

**Problem3:** Check for a context-free language is decidable.

There is a context-free grammar **G** for a context-free language **L**, and an input string **w**. The Turning Machine **M** decides on input **(G,w)**. If it accepts, then in accept state and if it rejects, then in reject state. So, context-free language is decidable.

Recursively Enumerable Language