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. Elke klasse in de chomskyhiërarchie omvat ook de klassen met een hoger nummer. De hiërarchie is genoemd naar haar uitvinder, de Amerikaanse taalkundige Noam Chomsky, en werd het eerst beschreven in 1956.
Type Taalklasse Automatenmodel Grammatica Type 3 Regulier Eindige automaat Reguliere grammatica Type 2 Contextvrij Stapelautomaat, ook bekend als push-down automaat Contextvrije grammatica Type 1 Contextgevoelig Lineair begrensde turingmachine Contextgevoelige grammatica Type 0 Semi-beslisbaar Turingmachine elke grammatica geen type Alle talen Geen Geen
Complexiteit De indeling naar type in dit geval zegt direct iets over de uitdrukkingskracht, maar met name ook de complexiteit van generatie en interpretatie. Talen uit een klasse met een hoger Chomsky-type zijn eenvoudiger van vorm dan talen uit een lagere klasse, maar ze kunnen wel veel eenvoudiger herkend en gegenereerd worden.
Toepasbaarheid 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 maar ook binnen andere formele kaders.
Literatuur
Categorie:Generatieve taalkunde Categorie:Syntaxis (taalkunde) Categorie:Formele taal