Language Decidability - Automata Theory

What is Language Decidability?

A language is mentioned as Decidable or Recursive in case of Turing machine which supports and provides every input string w. Here each decidable language is known as Turing-Acceptable.

decidability_and_decidable_languages

A decision problem P is decidable incase the language L of all yes instances to P is decidable.

For any decidable language, each input string known as the TM halts either known as the accept or the reject state as mentioned in the following diagram −

Example 1

See if the accompanying issue is decidable or not −

Is a number 'm' prime?

Solution

Prime numbers = {2, 3, 5, 7, 11, 13, … ..}

Partition the number 'm' by every one of the numbers in the vicinity of '2' and '√m' beginning from '2'.

On the off chance that any of these numbers create a leftover portion zero, at that point it goes to the "Rejected state", else it goes to the "Acknowledged state". Along these lines, here the appropriate response could be made by 'Yes' or 'No'.

Hence, it is a decidable problem.

Example 2

Given a regular language L and string w, how can we check if w ∈ L?

Solution

Take the DFA that accepts L and check if w is accepted

dfa1

Some more decidable problems are −

  • Does DFA accept the empty language?
  • Is L1 ∩ L2 = ∅ for regular sets?

Note

  • If a language L is decidable, then its complement L' is also decidable
  • If a language is decidable, then there is an enumerator for it.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics