Arrange the following families of languages from specialization to generalization, defined over alphabet $$\Sigma$$​:
A. Family of all regular languages.
B. Family of all Turing acceptable languages.
C. Family of all Turing decidable languages.
D. Family of all context free languages.
Choose the correct answer from the options given below:

Correct option is C

The families of formal languages can be arranged according to their expressive power, from the most specialized/restricted class to the most general/powerful class. Regular languages are the most restricted among the four, because every regular language can be recognized by a finite automaton.
Context-free languages are more expressive than regular languages because they can describe languages requiring constructs such as balanced parentheses. Turing-decidable languages are more powerful still, because a Turing machine that decides a language must halt on every input.
Finally, Turing-acceptable (recursively enumerable) languages form a broader class: a Turing machine is guaranteed to accept strings in the language but may run forever on strings outside it. Thus, the containment is A ⊂ D ⊂ C ⊂ B, giving A, D, C, B.
Information Booster
1. Hierarchy of the Language Families
The relevant hierarchy is:
Regular ⊂ Context-Free ⊂ Turing-Decidable ⊂ Turing-Acceptable
Therefore, A < D < C < B
This is a special case of the Chomsky hierarchy, extended beyond context-sensitive languages to distinguish decidable and recognizable languages.
2. Regular Languages — A
A regular language is a language that can be recognized by a finite automaton, such as:
· DFA — Deterministic Finite Automaton
· NFA — Nondeterministic Finite Automaton
Regular languages can also be represented using:
· Regular expressions
· Regular grammars
· Finite automata
For example:
$$L=\{w\in\{0,1\}^*:w\text{ ends with }01\}$$​ is a regular language. Regular languages have limited memory, because a finite automaton has only a finite number of states.
Thus, among the given families, they are the most specialized/restricted:
A = Regular Languages
3. Context-Free Languages — D
A context-free language (CFL) is generated by a context-free grammar (CFG) and can be recognized by a pushdown automaton (PDA).
A standard example is:
​$$L=\{a^nb^n\mid n\geq0\}$$​​
This language is not regular, but it is context-free.
A PDA has a stack, giving it more memory capability than a finite automaton.
Therefore, Regular ⊊ Context-Free
4. Turing-Decidable Languages — C
A language is Turing decidable if there exists a Turing machine that:
· Accepts every string belonging to the language.
· Rejects every string not belonging to the language.
· Halts on every input.
Therefore, a decider always terminates.
For a language L, a decider M satisfies:
w ∈ L => M accepts w and w ∉ L => M rejects w with M halting in both cases.
Turing-decidable languages include all regular and context-free languages:
CFL ⊆ Decidable
Thus, A < D < C
5. Turing-Acceptable Languages — B
A Turing-acceptable language is also commonly called a:
· Turing-recognizable language
· Recursively enumerable (RE) language
A Turing machine recognizing such a language has the following behavior:
· If w ∈ L, it eventually accepts.
· If w ∉ L, it may reject or run forever.
The crucial difference is that the machine is not required to halt for every input.
Therefore, every decidable language is Turing-acceptable:
Decidable ⊆ Turing-Acceptable but the reverse is not true.
Thus, A < D < C < B
6. Why Turing-Acceptable Languages Are More General Than Decidable Languages?
Consider the halting problem:
HALT = {⟨M, w⟩∣M halts on w}
The halting problem is Turing-acceptable/recognizable, but it is not decidable.
A Turing machine can simulate M on w:
· If M halts, accept.
· If M never halts, the simulation continues forever.
Therefore, the language can be recognized but cannot be decided.
This demonstrates, Decidable ⊊ Turing-Acceptable
7. Comparison Table

Hence, A ⊂ D ⊂ C ⊂ B
8. Chomsky Hierarchy Connection
The traditional Chomsky hierarchy is:
Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable
The question additionally introduces Turing-decidable languages between context-free and Turing-acceptable languages:
Regular ⊂ Context-Free ⊂ Decidable ⊂ Turing-Acceptable