Mal:Formelle språk og grammatikkar
| Automatteori: formelle språk og formell grammatikk | |||
|---|---|---|---|
| Chomsky- hierarkiet |
Grammatikkar | Språk | Minimal automat |
| Type-0 | Uavgrensa | Rekursivt nummererbare | Turingmaskin |
| (ikkje med) | (ikkje noko felles namn) | Rekursive | Decider |
| Type-1 | Kontekst-sensitiv | Kontekst-sensitive | Lineært bunde |
| Type-2 | Kontekst-fri | Kontekst-fri | Pushdown |
| Type-3 | Regulær | Regulær | Finitt |
| Kvar kategori av språk eller grammatikkar er eit ordentleg subsett av kategorien rett over han. | |||