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

Lo stesso argomento in dettaglio: Grammatica formale.

Come le altre grammatiche formali, è una quadrupla ${\displaystyle {\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle }$, in cui

1. ${\displaystyle N}$ sono i simboli non terminali
2. ${\displaystyle \Sigma }$ sono i simboli terminali
3. ${\displaystyle S\in N}$ detto assioma è il simbolo non terminale di inizio.
4. ${\displaystyle P}$ sono le regole di produzione, una relazione binaria di cardinalità finita su ${\displaystyle (N\cup \Sigma )^{*}\circ N\circ (N\cup \Sigma )^{*}\times (N\cup \Sigma )^{*}}$, che normalmente scriviamo come ${\displaystyle \alpha \to \beta }$

   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)

${\displaystyle A\to \beta ,A\in N,\beta \in (N\circ \Sigma )\cup \Sigma }$

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)

${\displaystyle A\to \beta ,A\in N,\beta \in (\Sigma \circ N)\cup \Sigma }$

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 ${\displaystyle {\mathcal {G}}}$ 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 ${\displaystyle {\mathcal {G}}'}$ formata dalla grammatica ${\displaystyle {\mathcal {G}}}$ a cui sono state eliminate le produzioni vuote.
Più formalmente ${\displaystyle {\mathcal {G}}'}$ regolare senza ε-produzioni tale che ${\displaystyle L({\mathcal {G}}')=L({\mathcal {G}})-\{\varepsilon \}}$

Esempi

Un esempio di grammatica lineare destra ${\displaystyle {\mathcal {G}}}$ con ${\displaystyle N=\{S\},\Sigma =\{a,b\},S}$ assioma, ${\displaystyle P}$ formato dalle seguenti regole di produzione:

${\displaystyle S\to aS}$

${\displaystyle S\to b}$

Questa grammatica descrive lo stesso linguaggio dell'espressione regolare ${\displaystyle a^{*}b}$.

Un altro esempio di grammatica lineare destra ${\displaystyle {\mathcal {G}}}$ con ${\displaystyle N=\{S,C\},\Sigma =\{a,b,c\},S}$ assioma, ${\displaystyle P}$ formato dalle seguenti regole di produzione:

${\displaystyle S\to aS}$

${\displaystyle S\to bC}$

${\displaystyle S\to b}$

${\displaystyle C\to cC}$

${\displaystyle C\to c}$

Questa grammatica descrive lo stesso linguaggio dell'espressione regolare ${\displaystyle a*bc*}$.

Esempio di grammatica non regolare

Una grammatica che genera il linguaggio ${\displaystyle L=\{a^{i}b^{i}\;|\;i\geq 0\}}$ può essere ${\displaystyle {\mathcal {G}}}$ con ${\displaystyle N=\{S,A\},\Sigma =\{a,b\},S}$ assioma, ${\displaystyle P}$ formato dalle seguenti regole di produzione:

${\displaystyle S\to aA}$

${\displaystyle A\to Sb}$

${\displaystyle S\to \varepsilon }$

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 degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sovrastante.

Portale Informatica

Portale Linguistica