De Chomskyhiërarchie is een indeling in klassen van de formele talen naar het type formele grammatica dat alle talen binnen een bepaalde klasse kan genereren. De hiërarchie is genoemd naar haar uitvinder, de Amerikaanse taalkundige Noam Chomsky.
Hoewel de indeling vooral binnen de theoretische informatica gebruikt wordt, is ze ook gebruikt voor het onderzoek naar natuurlijke talen, binnen het kader van de generatieve taalkunde.
| Taalklasse |
Model van berekenbaarheid |
Grammatica |
| Regulier |
Eindige Automaat |
Reguliere grammatica |
| Contextvrij |
Stapelautomaat, ook bekend als push-down automaat |
Context-vrije grammatica |
| Contextgevoelig |
Lineair gebonden automaat |
Context-gevoelige grammatica |
| Turingbeslisbaar |
Turingmachine |
Onbeperkte grammatica |
| Turingonbeslisbaar |
Geen; deze talen zijn onberekenbaar |
Geen; onberekenbaar |
| Dit artikel is een beginnetje over taal. U wordt uitgenodigd op bewerk te klikken om uw kennis aan dit artikel toe te voegen. |
 |
