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. |