Limbaje independente de context

Un limbaj independent de context este un limbaj formal acceptat de un automat cu stivă. Limbajele independente de context pot fi generate de gramatici independente de context.

Exemple

Un exemplu tipic de limbaj independent de context este $L=\{a^{n}b^{n}:n\geq 1\}$, limbajul tuturor cuvintelor nevide de lungime pară, care au prima jumătate formată din $a$-uri, și a doua jumătate formată din $b$-uri. $L$ este generat de gramatica $S\to aSb~|~ab$, și este acceptat de automatul cu stivă $M=(\{q_{0},q_{1},q_{f}\},\{a\},\{a,b,z\},\delta ,q_{0},\{q_{f}\})$ unde $\delta$ este definit după cum urmează:

$\delta (q_{0},a,z)=(q_{0},a)$
$\delta (q_{0},b,ax)=(q_{1},x)$
$\delta (q_{1},b,ax)=(q_{1},x)$
$\delta (q_{1},b,bz)=(q_{f},z)$

Limbajele independente de context au multe aplicații în limbajele de programare; de exemplu, limbajul tuturor parantezelor corect închise este generat de gramatica $S\to SS~|~(S)~|~\lambda$. De asemenea, majoritatea expresiilor aritmetice sunt generate de gramatici independente de context.

Proprietăți de închidere

Familia limbajelor independente de context este închisă în raport cu operațiile de concatenare și reuniune dar nu în raport cu intersecția sau diferența. Totuși, este închisă în raport cu intersecția și diferența cu un limbaj regulat.

Alte legături

Există o lemă de pompare pentru limbaje independente de context, care dă o condiție necesară pentru ca un limbaj să fie independent de context.

Bibliografie

• Michael Sipser - "Introduction to the Theory of Computation", PWS Publishing, 1997, ISBN 0-534-94728-X Chapter 2: Context-Free Languages, pp.91–122.