Grammatica regolare

Una grammatica regolare, in informatica, è una grammatica formale generativa. Detta anche lineare destra o lineare sinistra, secondo la gerarchia di Chomsky è una grammatica di tipo-3.

Richiami 

Come le altre grammatiche formali, è una quadrupla , in cui
  sono i simboli non terminali
  sono i simboli terminali
  detto assioma è il simbolo non terminale di inizio.
  sono le regole di produzione, una relazione binaria di cardinalità finita su , che normalmente scriviamo come 
 questa scrittura ci dice che a sinistra ci deve essere almeno un non terminale ed a destra qualsiasi cosa.

Definizione 
Le produzioni di una grammatica regolare sono del tipo:
 nel caso di lineari sinistre (in inglese left regular grammar)

ossia a sinistra della regola di produzione c'è un non terminale e a destra un non terminale seguito da un terminale oppure un singolo terminale.

 nel caso di lineari destre (in inglese right regular grammar)

ossia a sinistra della regola di produzione c'è un non terminale e a destra un terminale seguito da un non terminale oppure un singolo terminale.

Poniamo attenzione al fatto che non ci devono essere produzioni miste formate da lineari destre e sinistre contemporaneamente nella stessa grammatica, poiché in questo caso non siamo più in presenza di una grammatica regolare ma ad una grammatica libera dal contesto (non contestuale) come evidenziato in un esempio seguente.

Vengono chiamate regolari perché i linguaggi generati da queste grammatiche sono rappresentabili tramite espressioni regolari.
Il termine lineare deriva dal fatto che a destra delle produzioni possiamo trovare al massimo un non terminale; destra o sinistra indica dove il non terminale sarà rispetto al terminale.

I linguaggi generabili da grammatiche regolari (di tipo-3) sono detti linguaggi regolari e sono equivalenti ai linguaggi riconosciuti dagli automi a stati finiti ed ai linguaggi rappresentati da espressioni regolari.

Ogni grammatica regolare è anche una grammatica libera dal contesto visto che le grammatiche tipo-3 sono strettamente contenute in quelle tipo-2 secondo la gerarchia di Chomsky.

Alcuni libri di testo e articoli non ammettono regole di produzione vuote (ε-produzioni), e assumono che la stringa vuota non sia presente nel linguaggio.
Ad ogni modo è dimostrato il teorema che garantisce che data una grammatica  le cui regole di produzione P possono essere separate in due sottoinsiemi contenenti uno le produzioni vuote e l'altro le produzioni di tipo regolare, allora esiste una grammatica regolare  formata dalla grammatica  a cui sono state eliminate le produzioni vuote.
Più formalmente  regolare senza ε-produzioni tale che

Esempi 
Un esempio di grammatica lineare destra  con  assioma,  formato dalle seguenti regole di produzione:
 
 
Questa grammatica descrive lo stesso linguaggio dell'espressione regolare .

Un altro esempio di grammatica lineare destra  con  assioma,  formato dalle seguenti regole di produzione:
 
 
 
 
 
Questa grammatica descrive lo stesso linguaggio dell'espressione regolare .

Esempio di grammatica non regolare 
Una grammatica che genera il linguaggio  può essere  con  assioma,  formato dalle seguenti regole di produzione:
 
 
 
ma questa non è una grammatica regolare bensì una grammatica libera dal contesto; ha entrambe le produzioni, destre e sinistre, e quindi non è regolare.

Bibliografia 
 Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi. Linguaggi, Modelli, Complessità. Franco Angeli Editore, 2003 ISBN 88-464-4470-1

Voci correlate 
 Linguaggio regolare
 Automa a stati finiti
 Espressione regolare

 Grammatica lineare e linguaggio lineare

Teoria dei linguaggi formali