Grammatica lineare

Grammatica generativa le cui produzioni sono lineari, ossia del tipo:

• lineari destre
  • A --> aB
  • A --> a
• lineari sinistre
  • A --> Ba
  • A --> a

dove con A e B variabili (dell'alfabeto dei simboli non terminali) ed a simbolo dell'alfabeto terminale.

Tali grammatiche formano una classe detta delle grammatiche di tipo 3 nella gerarchia di Chomsky.

I linguaggi generati da tali grammatiche sono detti linguaggi lineari.

---

|