Informatik
Was ist die
Chomsky-Hierarchie
?
Die Chomsky-Hierarchie ordnet Grammatiken und Sprachen nach Ausdrucksstärke:
Typ 3: regulär.
Typ 2: kontextfrei.
Typ 1: kontextsensitiv.
Typ 0: rekursiv aufzählbar.
r
Typ 3
regulär
cf
Typ 2
kontextfrei
r->cf
subset
cs
Typ 1
kontextsensitiv
cf->cs
subset
re
Typ 0
rekursiv aufzählbar
cs->re
subset