Language Acceptance Checker

Chomsky Hierarchy: RL · CFL · CSL · REL — step-by-step verification

Language Class (Chomsky Hierarchy)

Regular Expression

Operators: | or + (union), * (Kleene star), () grouping. Literals: a–z 0–9 ε e.g. (0+1)* = {0,1}*

Test String (leave blank to test empty string)

Chomsky Hierarchy

Type 3 · RLRegular Grammar / DFA / NFA / RegEx

Type 2 · CFLContext-Free Grammar / PDA

Type 1 · CSLContext-Sensitive Grammar / LBA

Type 0 · RELUnrestricted Grammar / Turing Machine

Each class is a strict superset of the one above it.
RL ⊂ CFL ⊂ CSL ⊂ REL

Language Acceptance Checker

Select a language class, enter an expression or grammar,
provide a test string, then press Check.