Theory

Language Information

Reductions →

Computability reductions: transfer decidability and recognizability between languages.

Class Hierarchy

All Languagesco-ATMRecursively Enumerable (RE)ATMContext-FreeaⁿbⁿRegulara*b+

Closure Properties

OperationRegularCFLRE
Union✓✓✓
Intersection✓✗✓
Complement✓✗✗
Concatenation✓✓✓
Kleene star✓✓✓
Intersection with regular✓✓✓
Homomorphism✓✓✓
Inverse homomorphism✓✓✓
Reversal✓✓✓
Set difference✓✗✗

CFL = Context-Free · RE = Recursively Enumerable