Limbaj dependent de context
Un limbaj dependent de context (sau chiar contextual , legat de context sau contextual ) este un limbaj formal care poate fi definit de o gramatică dependentă de context . Este unul dintre cele patru tipuri de gramatică ale ierarhiei Chomsky . Este cel mai puțin utilizat, atât în teorie, cât și în practică.
Proprietăți de calcul
Computațional, un limbaj dependent de context este echivalent cu un automat liniar mărginit . Aceasta este o mașină Turing nedeterministă cu o panglică de numai kn celule, unde n este magnitudinea intrării și k este o constantă dependentă de mașină. Aceasta înseamnă că orice limbaj formal care poate fi decis de această mașină este un limbaj dependent de context și că orice limbaj dependent de context poate fi decis de o astfel de mașină.
Acest set de limbaje este, de asemenea, cunoscut sub numele de NLIN-SPACE , deoarece acestea pot fi acceptate folosind spațiul liniar pe o mașină de Turing nedeterministă . Clasa LIN-SPACE este definită în același mod, cu excepția faptului că folosește o mașină Turing deterministă. În mod clar, LIN-SPACE este un subset al unui NLIN-SPACE , dar nu se știe dacă LIN-SPACE = NLIN-SPACE . Se crede că nu sunt la fel.
Exemple
Un exemplu de limbaj în funcție de context , care nu este de context liber este L = {a p: p este un număr prim }. Cea mai simplă modalitate de a arăta că este un limbaj dependent de context este folosirea unui automat liniar mărginit . O dovadă că L nu este liber de context poate fi obținută de lema de pompare .
Proprietățile limbajelor dependente de context
- Unirea, intersecția și concatenarea a două limbi dependente de context este dependentă de context.
- Complementul unui limbaj dependent de context este el însuși dependent de context.
- Fiecare limbaj fără context face parte, de asemenea, din setul de limbi dependente de context.
Bibliografie
- Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Limbaje de modelare a complexității, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1 .