Grammatica regolare: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Definizione: Le due definizioni erano invertite. |
m Bot: formattazione dei wikilink; modifiche estetiche |
||
Riga 1:
[[
Una '''grammatica regolare''', è una [[grammatica formale]] [[grammatica generativa|generativa]]. Detta anche '''lineare destra''' o '''lineare sinistra''', secondo la [[gerarchia di Chomsky]] è una grammatica di tipo-3.
Riga 6:
{{vedi anche|grammatica formale}}
Come le altre grammatiche formali, è una [[N-pla|quadrupla]] <math>\mathcal{G} = \left \langle N, \Sigma, P, S \right \rangle</math>, in cui
# <math>N</math> sono i simboli non terminali
# <math>\Sigma</math> sono i simboli terminali
# <math>S \in N</math> detto ''assioma'' è il simbolo non terminale di inizio.
# <math>P</math> sono le regole di produzione, una relazione binaria di cardinalità finita su <math>(N \cup \Sigma)^* \circ N \circ (N \cup \Sigma)^* \times (N \cup \Sigma)^*</math>, che normalmente scriviamo come <math>\alpha \to \beta</math>
#: 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'')
:<math>A \to \beta, A \in N, \beta \in (N \circ \Sigma) \cup \Sigma</math><br />
: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'')
:<math>A \to \beta, A \in N, \beta \in (\Sigma \circ N) \cup \Sigma</math><br />
: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.
Riga 25:
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 [[espressione regolare|espressioni regolari]].<br />
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 [[linguaggio regolare|
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.<br />
Ad ogni modo è dimostrato il teorema che garantisce che data una grammatica <math>\mathcal{G}</math> 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 <math>\mathcal{G}'</math> formata dalla grammatica <math>\mathcal{G}</math> a cui sono state eliminate le produzioni vuote.<br />
Più formalmente <math>\mathcal{G}'</math> regolare senza ε-produzioni tale che <math>L(\mathcal{G}') = L(\mathcal{G}) - \{\varepsilon\}</math>
Riga 58:
== 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]]
{{Linguaggi formali e grammatiche}}
| |||