O gramatică dependentă de context ( KZ-gramatică , gramatică de context ) este un caz special de gramatică formală (tip 1 conform ierarhiei Chomsky ), în care părțile din stânga și din dreapta ale tuturor producțiilor pot fi înconjurate de terminale și non-terminale. simboluri.
Un caz special de gramatică formală este și gramatica fără context .
O limbă care poate fi specificată de o gramatică CV este numită limbă dependentă de context sau limbaj CV.
O gramatică formală G=(N, T, I, P) este sensibilă la context dacă toate regulile lui P sunt de forma: αAβ → αωβ
unde A ∈ N (adică un singur simbol non-terminal), ω ∈ (N ∪ T) + (adică un șir nevid format din simboluri terminale și/sau non-terminale), α, β ∈ ( N ∪ T)* (adică orice șir format din caractere terminale și/sau non-terminale).
Următoarea gramatică specifică o limbă sensibilă la context :
Așa arată lanțul de generație aaa bbb ccc:
Limbi formale și gramatici formale | |
---|---|
Concepte generale | |
Tip 0 | |
Tipul 1 |
|
Tip 2 | |
Tip 3 | |
analizare |