Gramatică dependentă de context

O gramatică contextuală (sau contextuală, contextuală sau chiar contextuală) este o gramatică formală în care forma producțiilor restrânge aplicația numai în anumite contexte. Gramaticile dependente de context sunt mai generale și mai puternice decât cele fără context și sunt ele însele mai puțin generale decât gramaticile structurii frazelor. Limbile descrise de gramaticile dependente de context pot fi recunoscute de automate liniare .

Conceptul de gramatică dependentă de context a fost introdus de Noam Chomsky în anii 1950 ca o modalitate de a descrie sintaxa unui limbaj natural în care există adesea că un cuvânt poate sau nu să fie adecvat într-o anumită poziție, în funcție de context. În ierarhia Chomsky, gramaticile dependente de context sunt numite Tip 1. Un limbaj formal care poate fi descris de o gramatică dependentă de context este numit limbaj dependent de context (sau Tip 1).

Definiție formală

O gramatică dependentă de context este o gramatică formală G = ( N , Σ, P , S ) astfel încât toate regulile de producție din P sunt de forma

α A β → αγβ

cu A în N (adică, A este un simbol non-terminal ) și α și β în ( N U Σ) * (adică șirurile α și β ale simbolurilor non-terminale și terminale ) și γ în ( N U Σ) ⁺ (adică, γ un șir ne-gol de terminale și non-terminale). Corzile $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ Și $\beta$ ${\ displaystyle \ beta}$ $\ beta$ pot fi goale, dar $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ nu trebuie să fie gol. Regula de producție S → ε este permisă dacă S nu apare în partea dreaptă a vreunei reguli de producție.

Numele dependent de context este explicat de α și β care formează contextul lui A și determină dacă A poate fi înlocuit cu γ sau nu. Cu toate acestea, într -o gramatică fără context , contextul unui non-terminal nu este luat în considerare.

Definiție alternativă

O clasă mai generală este cea a gramaticilor monotone . O gramatică este monotonă dacă fiecare regulă de producție este de formă

α → β cu | α | ≤ | β |

unde | α | este lungimea lui α (adică numărul de simboluri ale lui α); regula de producție S → ε este, de asemenea, permisă, dacă S nu apare în partea dreaptă a vreunei reguli de producție.

O astfel de gramatică se numește monotonă, deoarece niciuna dintre reguli nu reduce dimensiunea șirului care este rescris.

Este ușor să ne dăm seama că fiecare gramatică dependentă de context este monotonă, dar există gramatici monotone care nu sunt dependente de context (urmează un exemplu în scurt timp). Cu toate acestea, clasa limbilor care pot fi descrise de gramaticile dependente de context coincide cu cea a limbilor care pot fi descrise de gramaticile monotone. Dacă un limbaj formal L poate fi descris de o gramatică monotonă, atunci este posibil să se construiască o gramatică dependentă de context care să descrie L.

Exemplu

O simplă gramatică monotonă este

S → abc | la SB c

c B → B c

b B → bb

unde | este folosit pentru a separa diferite opțiuni ale aceluiași non-terminal. Această gramatică generează limbaj $\{a^{n}b^{n}c^{n}:n\geq 1\}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n}: n \ geq 1 \}}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n}: n \ geq 1 \}}$ , care nu este liber de context . Această gramatică nu depinde de context, deoarece în producția celei de-a doua linii partea dreaptă nu începe cu terminalul c cu care începe partea stângă. O gramatică dependentă de context pentru aceeași limbă este

$S\rightarrow aSBC$ ${\ displaystyle S \ rightarrow aSBC}$ ${\ displaystyle S \ rightarrow aSBC}$
$S\rightarrow aBC$ ${\ displaystyle S \ rightarrow aBC}$ ${\ displaystyle S \ rightarrow aBC}$
$CB\rightarrow HB$ ${\ displaystyle CB \ rightarrow HB}$ ${\ displaystyle CB \ rightarrow HB}$
$HB\rightarrow HC$ ${\ displaystyle HB \ rightarrow HC}$ ${\ displaystyle HB \ rightarrow HC}$
$HC\rightarrow BC$ ${\ displaystyle HC \ rightarrow BC}$ ${\ displaystyle HC \ rightarrow BC}$
$aB\rightarrow ab$ ${\ displaystyle aB \ rightarrow ab}$ ${\ displaystyle aB \ rightarrow ab}$
$bB\rightarrow bb$ ${\ displaystyle bB \ rightarrow bb}$ ${\ displaystyle bB \ rightarrow bb}$
$bC\rightarrow bc$ ${\ displaystyle bC \ rightarrow bc}$ ${\ displaystyle bC \ rightarrow bc}$
$cC\rightarrow cc$ ${\ displaystyle cC \ rightarrow cc}$ ${\ displaystyle cC \ rightarrow cc}$

Gramaticile mai complexe pot fi date pentru alte limbi dependente de context, cum ar fi $\{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n}: n \ geq 1 \}}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n}: n \ geq 1 \}}$ .

Forme normale

Orice gramatică dependentă de context care nu generează șirul gol poate fi transformată într-o gramatică echivalentă în formă normală Kuroda . Echivalent înseamnă că generează același limbaj.

Proprietăți de calcul

Problema de a decide dacă un anumit șir de caractere s aparține limbajului unei anumite gramatica nu este liber de context G este PSPACE-completă . Desigur, există și unele gramatici dependente de context a căror problemă de recunoaștere gramaticală este PSPACE-completă.

Bibliografie

Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Limbaje de modelare a complexității, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1 .

Elemente conexe

Ierarhia Chomsky

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.