Language Information

Computability reductions: transfer decidability and recognizability between languages.

Class Hierarchy

Operation	Regular	CFL	RE
Union	✓	✓	✓
Intersection	✓	✗	✓
Complement	✓	✗	✗
Concatenation	✓	✓	✓
Kleene star	✓	✓	✓
Intersection with regular	✓	✓	✓
Homomorphism	✓	✓	✓
Inverse homomorphism	✓	✓	✓
Reversal	✓	✓	✓
Set difference	✓	✗	✗

CFL = Context-Free · RE = Recursively Enumerable