Chomskyhiërarchie
Uit Wikipedia, de vrije encyclopedia
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]
Meer informatie Type, Taalklasse ...
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 |
Sluiten