How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The inclusions in the language-class ladder are proper
Statement
For every fixed finite alphabet with at least two symbols, the containments in The regular, context-free, decidable, and recognizable language-class ladder are all strict:
Facts & Assumptions
Given: The classes from The regular, context-free, decidable, and recognizable language-class ladder over a finite alphabet containing distinct symbols .
Every regular language satisfies the pumping property from The pumping lemma for regular languages.
Membership in a context-free language is decidable, by Context-free-language membership is decidable.
Every context-free language satisfies the pumping property from The pumping lemma for context-free languages.
is computably enumerable, by The Turing-machine acceptance problem is computably enumerable complete.
is undecidable, by The Turing-machine acceptance problem is undecidable.
Proof
If a language is regular, choose a DFA recognizing it. Make one CFG whose variables are the states of , whose start variable is the start state, whose productions are for each transition, and whose accepting states also have productions . Then the grammar generates exactly the words accepted by . Hence every regular language is context-free.
Every decidable language is recognizable by running its decider and accepting exactly when the decider accepts. Thus
The language is context-free, for example via the grammar . It is not regular: if it were regular, [L1] would give a pumping length , but cannot be pumped inside the first symbols without changing the number of 's and leaving the number of 's fixed. Therefore
Relabel the binary alphabet of injectively by the two chosen symbols . This computable letter-by-letter bijection preserves recognizability and decidability. By [L5] and [L6], the relabeled language over is computably enumerable but not decidable. Therefore
Every context-free language is decidable by [L2], so
The language is decidable by checking the three blocks and comparing their lengths. It is not context-free: if were a pumping length from [L3], then a pumping window of length at most in could meet at most two consecutive blocks and could not meet both -blocks. Pumping a nonempty part therefore changes at least one of the three required counts without changing all three equally, or destroys the block order. This contradicts [L3]. Hence
Steps 2.1, 4.1, and 2.2 prove that all three containments are strict over the fixed alphabet .
Depends on
- The regular, context-free, decidable, and recognizable language-class ladder
- The pumping lemma for regular languages
- The pumping lemma for context-free languages
- The language generated by a CFG
- Context-free-language membership is decidable
- The Turing-machine acceptance problem is computably enumerable complete
- The Turing-machine acceptance problem is undecidable
Used by
Dependency tree · two levels
25 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- John Watrous, Introduction to the Theory of Computing (standard reference, not scraped)