Grammatica regolare: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
→Definizione: descrizione sbagliata della formula.. semplicemente erano invertite. per verifica vedere "Introduction to the theory of computation" di Michael Sipser |
||
Riga 16:
* nel caso di '''lineari destre''' (in inglese ''right regular grammar'')
:<math>A \to \beta, A \in N, \beta \in (N \cup \Sigma) \circ \Sigma</math><br/>
:ossia a sinistra della regola di produzione c'e' un non terminale e a destra un non terminale seguito da un
* nel caso di '''lineari sinistre''' (in inglese ''left 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
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.
|