Grammatica regolare

Da Wikipedia, l'enciclopedia libera.
Gerarchia-di-Chomsky.jpg

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

Richiami[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi grammatica formale.

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

  1. N sono i simboli non terminali
  2. \Sigma sono i simboli terminali
  3. S \in N detto assioma è il simbolo non terminale di inizio.
  4. P sono le regole di produzione, una relazione binaria di cardinalità finita su (N \cup \Sigma)^* \circ N \circ (N \cup \Sigma)^* \times (N \cup \Sigma)^*, che normalmente scriviamo come \alpha \to \beta
    questa scrittura ci dice che a sinistra ci deve essere almeno un non terminale ed a destra qualsiasi cosa.

Definizione[modifica | modifica wikitesto]

Le produzioni di una grammatica regolare sono del tipo:

  • nel caso di lineari sinistre (in inglese left regular grammar)
A \to \beta, A \in N, \beta \in (N \circ \Sigma) \cup \Sigma
ossia a sinistra della regola di produzione c'e' 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)
A \to \beta, A \in N, \beta \in (\Sigma \circ N) \cup \Sigma
ossia a sinistra della regola di produzione c'e' 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 \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 \mathcal{G}' formata dalla grammatica \mathcal{G} a cui sono state eliminate le produzioni vuote.
Più formalmente \mathcal{G}' regolare senza ε-produzioni tale che L(\mathcal{G}') = L(\mathcal{G}) - \{\varepsilon\}

Esempi[modifica | modifica wikitesto]

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

S \to aS
S \to b

Questa grammatica descrive lo stesso linguaggio dell'espressione regolare a^*b.

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

S \to aS
S \to bC
S \to b
C \to cC
C \to c

Questa grammatica descrive lo stesso linguaggio dell'espressione regolare a*bc*.

Esempio di grammatica non regolare[modifica | modifica wikitesto]

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

S \to aA
A \to Sb
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[modifica | modifica wikitesto]

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

Voci correlate[modifica | modifica wikitesto]

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 sottostante.