Grammatica regolare e irregolare
Inviato: 22/01/2015, 18:47
Salve a tutti,
qualcuno mi sa spiegare la differenza fra una grammatica regolare e una irregolare?
So che per i linguaggi si usa il Pumping Lemma, ma per la grammatica? Quali particolarità deve avere?
Una grammatica è regolare destra se ogni sua produzione è di una delle seguenti forme:
[math]
[math]
[math]
dove [math] è terminale e [math] e [math] sono non terminali.
Una grammatica è regolare sinistra se ogni sua produzione è di una delle seguenti forme:
[math]
[math]
[math]
dove [math] è terminale e [math] e [math] sono non terminali.
Una grammatica è irregolare se non è regolare destra e non è regolare sinistra.
Le grammatiche regolari destre (rispettivamente, sinistre) descrivono tutti e soli i linguaggi regolari. Quindi il Pumping Lemma vale anche per le grammatiche regolari. Il Pumping Lemma esprime una proprietà "semantca" dei linguaggi, non una proprietà "sintattica". Vale a dire che, a prescindere dal formalismo che usi per descrivere un linguaggio regolare, il Pumping Lemma vale nello stesso modo.
Aggiungerei anche che se G è una grammatica regolare sinistra, allora esiste G' grammatica regolare destra che genera lo stesso linguaggio generato da G.
qualcuno mi sa spiegare la differenza fra una grammatica regolare e una irregolare?
So che per i linguaggi si usa il Pumping Lemma, ma per la grammatica? Quali particolarità deve avere?
Una grammatica è regolare destra se ogni sua produzione è di una delle seguenti forme:
[math]
[math]
[math]
dove [math] è terminale e [math] e [math] sono non terminali.
Una grammatica è regolare sinistra se ogni sua produzione è di una delle seguenti forme:
[math]
[math]
[math]
dove [math] è terminale e [math] e [math] sono non terminali.
Una grammatica è irregolare se non è regolare destra e non è regolare sinistra.
Le grammatiche regolari destre (rispettivamente, sinistre) descrivono tutti e soli i linguaggi regolari. Quindi il Pumping Lemma vale anche per le grammatiche regolari. Il Pumping Lemma esprime una proprietà "semantca" dei linguaggi, non una proprietà "sintattica". Vale a dire che, a prescindere dal formalismo che usi per descrivere un linguaggio regolare, il Pumping Lemma vale nello stesso modo.
Aggiungerei anche che se G è una grammatica regolare sinistra, allora esiste G' grammatica regolare destra che genera lo stesso linguaggio generato da G.