Gramatica liniară

O gramatică liniară este o gramatică formală generativă .

În special, este o gramatică fără context ( non-contextuală ) în care partea dreaptă a producțiilor conține cel mult un non-terminal.

Cazurile speciale de gramatici liniare sunt gramatice obișnuite, deoarece pot fi liniare dreapta sau liniară stânga .

Definiție

Producțiile unei gramatici liniare sunt de tipul:

A\to \beta ,A\in N,\beta

{\ displaystyle A \ to \ beta, A \ în N, \ beta}

{\ displaystyle A \ to \ beta, A \ în N, \ beta}

cu cel mult un non-terminal.

Limbile care pot fi generate cu ajutorul gramaticilor liniare se numesc limbi liniare . Se poate arăta că această clasă de limbi este strict conținută în cea de context limbi (non-contextuale) și strict conține cea a limbilor obișnuite .

Exemplu

O gramatică liniară cu următoarele reguli de producție:

S → aSb

S → ab

generează limbaj $L=\{a^{i}b^{i}\;|\;i\geq 1\}$ ${\ displaystyle L = \ {a ^ {i} b ^ {i} \; | \; i \ geq 1 \}}$ ${\ displaystyle L = \ {a ^ {i} b ^ {i} \; | \; i \ geq 1 \}}$ nu se poate genera cu o gramatică obișnuită .

Bibliografie

Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi. Limbi, modele, complexitate . Franco Angeli Editore, 2003 ISBN 88-464-4470-1

Elemente conexe