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-
ADFA - {(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.
ANFA - {N,w}
When we convert NFA N to DFA D and run the Turning machine M for ADFA 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
