Classification of formal languages by generative power (Type 3 → Type 0)
RL Pumping Lemma Explorer
Verify or disprove pumping conditions for regular languages
If L is regular, ∃p≥1 s.t. ∀w∈L with |w|≥p, ∃xyz=w where:
(1) |xy|≤p (2) |y|≥1 (3) ∀i≥0, xyiz ∈ L
Pump length pString w
Split |x|Split |y|Pump i
Strategy for Minimum Pumping Length:
The minimum pumping length $p$ is the smallest integer where the rule holds. To find it, hunt for the shortest string in the language that cannot be pumped. If a string of length $k$ cannot be split into $xyz$ such that $xy^iz \in L$ for all $i \ge 0$, then $p$ must be at least $k+1$.
Closure Properties Table
Click operations to see which language classes are closed under each
CFL Pumping Lemma Explorer
Interactive tool for Context-Free Languages — Ogden's Lemma variant
If L is CFL, ∃p≥1 s.t. ∀w∈L with |w|≥p, ∃uvxyz=w where:
(1) |vxy| ≤ p (2) |vy| ≥ 1 (3) ∀i≥0: uvixyiz ∈ L
Pump length pString w
|u||v||x||y|Pump i
Decidability Reference
Decision problems by language class
Language Class
Membership
Emptiness
Equivalence
Universality
Regular (DFA)
Decidable
Decidable
Decidable
Decidable
CFL (CFG/DPDA/NPDA)
Decidable (CYK)
Decidable
Undecidable
Undecidable
CSL (LBA)
Decidable
Undecidable
Undecidable
Undecidable
RE (TM)
Semi-decidable
Undecidable
Undecidable
Undecidable
Non-RE
Undecidable
Undecidable
Undecidable
Undecidable
Rice-Shapiro Rule (Recognizability):
A property is Turing-recognizable (RE) if it satisfies the Finite Subset Rule (if $L$ has the property, a finite subset must trigger it) and Monotonicity (if finite $L_1$ has it, any $L_2 \supseteq L_1$ also has it). Properties like "is finite" or "is empty" fail these and are strictly unreachable by finite proof.
Green = Decidable (always halts, correct answer)
Orange = Semi-decidable (halts on yes, may loop on no)
Red = Undecidable (no algorithm exists)
Add Transition
Transition
From
Read
Stack
Pop
Push
Stack 2
Pop₂
Push₂
Tape
Write
Move
Output
Output
Probability
P
To
Configure State
Name
Use _, space or - to break long names onto multiple lines inside the node.
Start
Accept
Output λ
Priority Ω
Lower priorities dominate. Even accepts, odd rejects.