Grammatica regolare e irregolare

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

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

Torna a “[PRL] Programmazione I e laboratorio”