5.4Classifying a language
The idea
To classify a language, ask what it must remember or compare.
Think of it like this: Like triaging patients: the symptoms point to the right ward.
Why it exists
It is the fastest way to answer the "which class" questions.
How it works
- No unbounded memory: regular.
- One unbounded count or nesting: context-free (deterministic if no guessing).
- Two comparisons at once or copying: context-sensitive.
- Depends on whether a machine halts: RE or worse.
Worked example: Quick classification
{aⁿbⁿ} → DCFL. {wwᴿ} → CFL. {aⁿbⁿcⁿ}, {ww} → CSL. Halting language → RE not recursive.
Now play with it
- →Take the quiz of five languages.
What is the smallest class of this language? · question 1 of 5
{ aⁿbⁿ : n ≥ 1 }
Check yourself
Which language is NOT context-free?
Exam notes (the dense version)
Ask: does it need to count once (CFL), compare two things (CSL), or depend on halting behaviour (RE or worse)? aⁿbⁿ is DCFL; wwᴿ is CFL; aⁿbⁿcⁿ and ww are CSL but not CFL; the halting language is RE but not recursive.
Previous year questions: Language Hierarchy & Closure Tables (7)
PYQs are grouped by topic, so this is the full set for Language Hierarchy & Closure Tables; try the ones that match this subtopic. Open all 7 on the topic page.