| Problem | Regular | CFL | CSL | RE | |---------|---------|-----|-----|-----| | Membership (w ∈ L?) | Decidable | Decidable | Decidable | Undecidable (semi) | | Emptiness (L = ∅?) | Decidable | Decidable | Undecidable | Undecidable | | Finiteness | Decidable | Decidable | Undecidable | Undecidable | | Equivalence (L₁ = L₂?) | Decidable | Undecidable | Undecidable | Undecidable |
Design CFG for balanced parentheses.