Grammatica lineare

Da Wikipedia, l'enciclopedia libera.
Gerarchia-di-Chomsky.jpg

Una grammatica lineare è una grammatica formale generativa.

In particolare è una grammatica libera dal contesto (non contestuale) in cui la parte destra delle produzioni contiene al massimo un non terminale.

Casi particolari di grammatiche lineari sono le grammatiche regolari poiché possono essere lineari destre oppure lineari sinistre.

Definizione[modifica | modifica wikitesto]

Le produzioni di una grammatica lineare sono del tipo:

A \to \beta, A \in N, \beta con al massimo un non terminale.

I linguaggi generabili con grammatiche lineari sono detti linguaggi lineari. Si può dimostrare che questa classe di linguaggi è strettamente contenuta in quella dei linguaggi liberi dal contesto (non contestuali) e contiene strettamente quella dei linguaggi regolari.

Esempio[modifica | modifica wikitesto]

Una grammatica lineare con le seguenti regole di produzione:

S → aSb
S → ab

genera il linguaggio L = \{a^ib^i\; |\; i \ge 1\} non generabile con una grammatica regolare.

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • Giorgio Ausiello, Fabrizio d’Amore, Giorgio Gambosi. Linguaggi, Modelli, Complessità. Franco Angeli Editore, 2003 ISBN 88-464-4470-1