Definizione generale di grammatica

Le grammatiche context-free sono un caso particolare della definizione generale di grammatica.

In generale, una grammatica è una quadrupla $G = \lang V, T, P, S\rang$, in cui:

• $V$ è l’insieme finito dei simboli non-terminali
• $T$ è l’insieme finito dei simboli terminali
• $P$ è l’insieme finito delle regole di produzione, che sono coppie $\alpha \rarr \beta$ dove:
  • $\alpha \in (T \cup V)^+$, la testa della produzione, è una sequenza non vuota di simboli terminali e non-terminali
  • $\beta\in(T\cup V)^*$, il corpo della produzione, è una sequenza (possibilmente vuota) di simboli terminali e non-terminali
• $S\in V$ è il simbolo iniziale della grammatica.

L’unica cosa che cambia rispetto alla definizione di CFG è la forma delle regole di produzione: mentre nelle CFG la testa doveva essere un simbolo non terminale, qui può essere un’arbitraria stringa non vuota sull’insieme dei terminali e non-terminali della grammatica.

Derivazioni e linguaggio generato

Data una grammatica $G = \lang V, T, P, S\rang$,

• Si definisce la relazione di derivazione $\Rightarrow_G$ nel modo seguente: date $\alpha, \beta, \gamma, \delta \in (T\cup V)^*$, con $\alpha \neq \epsilon$, si ha $\gamma\alpha \delta \Rightarrow_G \gamma\beta \delta$ se $\alpha \rarr \beta$ è una produzione in $P$.

  In pratica, un passo di derivazione consiste nella sostituzione di una stringa con un’altra secondo una regola di produzione. Questa è una generalizzazione del passo di derivazione per le CFG, nel quale si sostituiva un singolo simbolo non-terminale con una stringa.

• La relazione di derivazione in zero o più passi, $\xRightarrow *_G$, è la chiusura riflessiva e transitiva di $\Rightarrow_G$ (esattamente come nel caso delle CFG).

• Il linguaggio generato da $G$ è l’insieme di stringhe terminali derivabili in zero o più passi dal simbolo iniziale di $G$,

  $$ L(G)= \{w \in T^* \ | \ S \xRightarrow * _G w\} $$

  (esattamente come nel caso delle CFG).

Esempio

Gerarchia di Chomsky

La gerarchia di Chomsky è una gerarchia di tipi di grammatiche, che a partire dalla definizione generale impone vincoli via via sempre più forti sulla forma delle regole di produzione, riducendo così la classe dei linguaggi generati. I livelli della gerarchia sono numerati da 0 a 3: numeri più grandi corrispondono a grammatiche più ristrette.

• Le grammatiche di tipo 0 sono le grammatiche nella loro definizione generale, che generano i linguaggi ricorsivamente enumerabili, riconosciuti dalle macchine di Turing.
• Le grammatiche di tipo 1, dette dipendenti dal contesto o context-sensitive, hanno produzioni $\alpha \rarr \beta$ (con $\alpha \in (T \cup V)^+$ e $\beta \in (T \cup V)^*$, come nella definizione generale) tali che $|\alpha|\leq |\beta|$ (intuitivamente, ciò significa che l’applicazione di una regola non accorcia mai la stringa che si sta derivando). Esse generano i linguaggi context-sensitive, riconosciuti dalle macchine di Turing linearmente limitate (cioè macchine di Turing con un vincolo sulla quantità di memoria utilizzata).
• Le grammatiche di tipo 2 sono le CFG, cioè hanno produzione del tipo $A\rarr \beta$ con $A\in V$ (e ancora $\beta \in (T \cup V)^*$). Esse generano i linguaggi context-free riconosciuti dagli automi a pila.
• Le grammatiche di tipo 3, dette regolari, sono quelle in cui ciascuna regola di produzione ha la forma $A\rarr aB$ oppure $A\rarr a$, con $A, B\in V$ e $a\in T$: la testa è ancora un simbolo non-terminale, come nelle CFG, ma il corpo può essere solo un simbolo terminale opzionalmente seguito da un non-terminale. Queste grammatiche generano la classe dei linguaggi regolari, per i quali costituiscono dunque un generatore alternativo alle espressioni regolari. Come già visto, i riconoscitori per i linguaggi regolari sono i vari tipi di automi a stati finiti: DFA, NFA e $\epsilon$-NFA.