Skip to main content
Link
Menu
Expand
(external link)
Document
Search
Copy
Copied
Home
Chomsky hierarchy
Regular
Grammars = DFA
Grammar forms
Membership computable
Linear
Grammars
Pumping lemma
Context-free
Equivalences
PDA = CFG
Mathlib equivalence
Acceptance modes
Pumping lemmas
Pumping lemma
Ogden's lemma
Closure
Substitution
Intersection
Right quotient
Decidability
aⁿbⁿcⁿ
Deterministic context-free
DPDA totalization
Complement
Closure properties
Context-sensitive
LBA equivalence
Grammar forms
Membership computable
⊊ Recursive
Recursive
Post's theorem
Complement
⊊ RE
Tape acceptance
Recursively enumerable
TM equivalence
Search procedures
Closure properties
Search Langlib
API Docs
GitHub
Context-free
Pumping lemmas
Pumping properties that bound the structure of context-free languages.
Table of contents
Pumping lemma
Ogden's lemma