Limbaje independente de context
De la Wikipedia, enciclopedia liberă
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.
Cuprins |
[modifică] Exemple
Un exemplu tipic de limbaj independent de context este 
, 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 
, şi este acceptat de automatul cu stivă M = ({q0,q1,qf},{a},{a,b,z},δ,q0,{qf}) unde δ este definit după cum urmează:
δ(q0,a,z) = (q0,a)
δ(q0,b,ax) = (q1,x)
δ(q1,b,ax) = (q1,x)
δ(q1,b,bz) = (qf,z)
Limbajele independente de context au multe aplicaţii în limbajele de programare; de exemplu, limbajul tuturor parantezelor corect închise este generat de gramatica 
. De asemenea, majoritatea expresiilor aritmetice sunt generate de gramatici independente de context.
[modifică] 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.
[modifică] 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.
[modifică] 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.
