Teoria automatelor : limbaje formale și gramatici formale | |||
---|---|---|---|
Ierarhia Chomsky | Gramatica formală | Limba | Automat minim |
Tipul-0 | (nelimitat) | Recursiv enumerabil | Mașină Turing |
(nelimitat) | Recursiv | Decider | |
Tipul 1 | Context dependent | Context dependent | Automat liniar |
Tipul 2 | Fără context | Fără context | Automat cu baterie ND |
Tipul 3 | Regulat | Regulat | Stări finite |
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia. |