Chomskyhiërarchie

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.^[1]

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.

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

↑ Chomsky, Noam (1956). Three models for the description of language. IRE Transactions on Information Theory (2): 113-124. Gearchiveerd van origineel op 23 september 2015.

[1] Chomsky, Noam (1956). Three models for the description of language. IRE Transactions on Information Theory (2): 113-124. Gearchiveerd van origineel op 23 september 2015.

[1]