Pagina 1 di 1

Grammatica regolare e irregolare

Inviato: 22/01/2015, 18:47
da InformateciBot
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.