Limbaje independente de context

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

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[modificare | modificare sursă]

Un exemplu tipic de limbaj independent de context este L = \{a^nb^n:n\geq1\}, 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[modificare | modificare sursă]

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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