Gerarchia di Chomsky: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Aggiungo: uk:Ієрархія Чомскі |
|||
Riga 32:
* Grammatiche di tipo-2 ([[grammatica libera dal contesto|grammatiche libere dal contesto]]) generano [[linguaggio libero dal contesto|linguaggi liberi dal contesto]]. Queste grammatiche sono definite da regole nella forma <math>A \rightarrow \gamma</math> con <math>A</math> simbolo non terminale e <math>\gamma</math> una stringa di simboli terminali e non terminali. Questi linguaggi sono esattamente tutti i linguaggi che possono essere riconosciuti da un [[automa a pila]] non deterministico. I linguaggi context free sono teoricamente le basi per la sintassi di molti [[linguaggio di programmazione|linguaggi di programmazione]] ([[Analisi sintattica]]).
* Grammatiche di tipo-3 ([[grammatica regolare|grammatiche regolari]]) generano [[linguaggio regolare|linguaggi regolari]]. Questo tipo di grammatiche restringe le sue regole ad un singolo simbolo non terminale nel lato sinistro della produzione e nel lato destro un singolo simbolo terminale, che può essere seguito (o preceduto, ma non entrambe le forme nella stessa grammatica) da un singolo simbolo non terminale. La regola <math>S \to \epsilon</math> è permessa anche qui se <math>S</math> non compare nel lati destri delle regole di produzione. Questi linguaggi sono esattamente tutti i linguaggi riconosciuti da un [[automa a stati finiti]]. Oltretutto, questa famiglia di linguaggi formali può essere ottenuta con [[espressione regolare|espressioni regolari]]. I linguaggi regolari sono comunemente usati per definire modelli di ricerca (search patterns) e la struttura lessicale dei linguaggi di programmazione ([[Analisi lessicale (informatica)|Analisi lessicale]]).
Nota che l'insieme delle grammatiche corrispondente ai linguaggi ricorsivi non è un membro di questa gerarchia.
| |||