Grammatica sintagmatica

La grammatica sintagmatica, altrimenti nota come gerarchia di Chomsky, è una gerarchia di contenimento delle classi delle grammatiche formali che genera i linguaggi formali. Questa gerarchia di grammatiche, dette anche grammatiche sintagmatiche, fu descritta da Noam Chomsky.

Grammatiche formali

Una grammatica formale consiste di una selezione finita di simboli terminali (le lettere delle parole in una lingua formale), una selezione di simboli non-terminali, una selezione finita di regole produttive con una porzione destra e una porzione sinistra che consistono di una parola di questi simboli e un simbolo di partenza. Una regola potrebbe essere applicata ad una parola sostituendo la parte sinistra con la parte destra. Una derivazione è una sequenza di applicazioni di regole. Una tale grammatica definisce il linguaggio formale di tutte le parole che consistono soltanto di simboli terminali che possono essere raggiunti da una derivazione del simbolo di partenza.

I simboli non terminali solitamente vengono rappresentati dalle lettere dei primi posti, quelli terminali dalle lettere degli ultimi e il simbolo di partenza da $S$. Per esempio la grammatica con simboli terminali $\{a,b\}$, nonterminali $\{S,A,B\}$ potrà avere come regole produttive:

$S$ → $ABS$

$S$ → ε (dove ε è la stringa vuota)

$BA$ → $AB$

$BS$ → $b$

$Bb$ → $bb$

$Ab$ → $ab$

$Aa$ → $aa$

e il simbolo di partenza $S$ definisce il linguaggio di tutte le parole che formano $a^{n}b^{n}$ (p.e. $n$ copie di $b$). Quella seguente è una grammatica più semplice che definisce un linguaggio simile: Terminali $\{p,q\}$, nonterminals $\{S\}$, simbolo di partenza $S$, regole produttive

$S$ → $pSq$

$S$ → ε