potrivit lui Noam Chomosky, există patru tipuri de gramatici − Tipul 0, tipul 1, tipul 2 și tipul 3. Următorul tabel arată modul în care acestea diferă unele de altele−
| Tip gramatică | gramatică acceptată | limbă acceptată | automat |
|---|---|---|---|
| Tip 0 | gramatică nerestricționată | limbaj recursiv enumerabil | mașină Turing |
| tip 1 | gramatică sensibilă la Context | limbaj sensibil la Context | automat liniar |
| tip 2 | Gramatică fără Context | limbă fără Context | automat de împingere |
| tip 3 | gramatică regulată | limbaj regulat | automat de stare finită |
aruncați o privire la următoarea ilustrație. Acesta arată domeniul de aplicare al fiecărui tip de gramatică –
Type-3 gramatică
type-3 gramatici genera limbi regulate. Gramaticile de tip 3 trebuie să aibă un singur non-terminal pe partea stângă și o parte dreaptă constând dintr-un singur terminal sau un singur terminal urmat de un singur non-terminal.
producțiile trebuie să fie în forma x aksqua a sau x aksqua aY
unde X, Y Aksqua n (non terminal)
și a xsqua t (Terminal)
regula s aksqua este permisă dacă s nu apare în partea dreaptă a vreunei reguli.
exemplu
X → ε X → a | aYY → b
gramatica de tip 2
gramatica de tip 2 generează limbi fără context.
producțiile trebuie să fie sub forma a
în care A n (non terminal)
și a n (t)* (șir de terminale și non-terminale).
aceste limbi generate de aceste gramatici sunt recunoscute de un automat de împingere nedeterminist.
exemplu
S → X a X → a X → aX X → abc X → ε
gramatica de tip 1
gramatica de tip 1 generează limbi sensibile la context. Producțiile trebuie să fie în formă
α O β → α γ β
unde O ∈ N (Non-terminal)
și α, β, γ ∈ (T ∪ N)* (Șiruri de terminale și non-terminale)
siruri De caractere α și β pot fi goale, dar γ trebuie să fie non-gol.
regula s este permisă dacă s nu apare în partea dreaptă a vreunei reguli. Limbile generate de aceste gramatici sunt recunoscute de un automat liniar delimitat.
exemplu
AB → AbBc A → bcA B → b
gramatica Type – 0
gramatica type-0 generează limbi recursiv enumerabile. Producțiile nu au restricții. Ele sunt orice gramatică a structurii de fază, inclusiv toate gramaticile formale.
generează limbile recunoscute de o mașină Turing.
producțiile pot fi sub formă de centimetrul, în cazul în care centimetrul este un șir de terminale și nonterminale cu cel puțin un terminal, iar centimetrul nu poate fi nul. -un șir de terminale și non-terminale.
Exemplu
S → ACaB Bc → acB CB → DB aD → Db