Контекстно-залежна граматика

Контекстно-залежна граматика (КЗ-граматика, контекстна граматика) - окремий випадок формальної граматики (тип 1 по ієрархії Хомського), у якій ліві і праві частини всіх продукцій можуть бути оточені термінальних і нетермінальних символів.

Окремим випадком формальної граматики так само є контекстно-вільна граматика.

Мова, який може бути заданий КЗ-граматикою, називається контекстно-залежним мовою чи КЗ-мовою.


Формальне визначення

Формальна граматика G = (N, T, I, P) є контекстно-залежною, якщо всі правила P мають вигляд: αAβ → αωβ

де A ∈ N (тобто одиночний нетермінальний символ), ω ∈ (N ∪ T) + (тобто непорожній ланцюжок, що складається з термінальних та / або нетермінальних символів), α, β ∈ (N ∪ T) * (тобто будь-яка ланцюжок, що складається з термінальних та / або нетермінальних символів).

Приклади

Наступна граматика задає контекстно-залежний мову \ {A ^ n b ^ n c ^ n: n \ ge 1 \} :

  1. S \ rightarrow aSBC
  2. S \ rightarrow aBC
  3. CB \ rightarrow HB
  4. HB \ rightarrow HC
  5. HC \ rightarrow BC
  6. aB \ rightarrow ab
  7. bB \ rightarrow bb
  8. bC \ rightarrow bc
  9. cC \ rightarrow cc


Так виглядає ланцюжок породження aaa bbb ccc:

S
\ Rightarrow_1 aSBC
\ Rightarrow_1 a \ boldsymbol {aSBC} BC
\ Rightarrow_2 aa \ boldsymbol {aBC} BCBC
\ Rightarrow_3 aaaB \ boldsymbol {HB} CBC
\ Rightarrow_4 aaaB \ boldsymbol {HC} CBC
\ Rightarrow_5 aaaB \ boldsymbol {BC} CBC
\ Rightarrow_3 aaaBBC \ boldsymbol {HB} C
\ Rightarrow_4 aaaBBC \ boldsymbol {HC} C
\ Rightarrow_5 aaaBBC \ boldsymbol {BC} C
\ Rightarrow_3 aaaBB \ boldsymbol {HB} CC
\ Rightarrow_4 aaaBB \ boldsymbol {HC} CC
\ Rightarrow_5 aaaBB \ boldsymbol {BC} CC
\ Rightarrow_6 aa \ boldsymbol {ab} BBCCC
\ Rightarrow_7 aaa \ boldsymbol {bb} BCCC
\ Rightarrow_7 aaab \ boldsymbol {bb} CCC
\ Rightarrow_8 aaabb \ boldsymbol {bc} CC
\ Rightarrow_9 aaabbb \ boldsymbol {cc} C
\ Rightarrow_9 aaabbbc \ boldsymbol {cc}