Decidable Language Classes

Exploring which formal language classes are decidable

Regular Languages

Regular languages are the simplest class of formal languages in the Chomsky hierarchy. They can be recognized by finite automata.

Theorem:

ADFA = {(B, w) | B is a DFA and B accepts the input string w} is decidable.

Proof Sketch:

  1. Construct a Turing machine M that takes (B, w) as input.
  2. M simulates the DFA B on input w.
  3. If the simulation ends in an accepting state of B, then M accepts w.
  4. If it ends in a non-accepting state of B, then M rejects w.

Since a DFA always terminates after processing the input string, M will always halt, making ADFA decidable.

Key Takeaways

  • ✓

    All regular, context-free, and context-sensitive languages are decidable

  • ✓

    A language is decidable if there exists a Turing machine that always halts and correctly accepts or rejects every input

  • ✓

    The decidability of these language classes is proven by constructing Turing machines that always halt