Plantilla:Llenguatges formals i gramàtiques - Viquipèdia, l'enciclopèdia lliure

Teoria d'autòmats: llenguatge formals i gramàtica formals

Jerarquia de Chomsky	Gramàtiques	Llenguatges	Màquines abstractes

Tipus-0 — Tipus-1 — — — — — Tipus-2 — — Tipus-3 — —	Sense restriccions (sense nom) Sensitiva al context Concatenació de rang Indexada — Sistema lineal de reescriptura lliure de context Adjunció d'arbres Lliure de context Lliure de context determinista Visibly pushdown Regular — No recursives	Enumerable recursivament Decidible Sensible al context Concatenació de rang^* Indexat^* — Llenguatge lineal de reescriptura lliure de context Adjunció d'arbres Lliure de context Lliure de context determinista Visibly pushdown Regular Lliure d'estrella Finit	Màquina de Turing Decider Linealment acotat Màquina de Turing PTIME Pila anidada Autòmat per subprocessos Autòmat amb pila d'arbre restringit Pila incrustada Autòmat amb pila no-determinista Autòmat amb pila determinista Visibly pushdown Finit Sense comptadors(amb monoides finits aperiòdics) Finit acíclic

Cada categoria de llenguatges, excepte aquells marcats per ^*, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia.