Контекстно-вільна граматика

Контекстно-вільна граматика ${\displaystyle G}$ — це четвірка ${\displaystyle (N,T,P,S)}$:

• ${\displaystyle S\in N}$
• ${\displaystyle N}$ та ${\displaystyle T}$ — скінченні множини, що не перетинаються
• ${\displaystyle P}$ — скінченна підмножина ${\displaystyle N\times (N\cup T)^{*}}$

Використовують такі назви: ${\displaystyle N}$ — множина нетермінальних символів, ${\displaystyle T}$ — множина термінальних символів, ${\displaystyle P}$ — множина правил виводу, ${\displaystyle S}$ — початковий символ. Правила ${\displaystyle (\alpha ,\beta )\in P}$ записують як ${\displaystyle \alpha \rightarrow \beta }$.

У лівій частині правила виводу має міститися одна змінна (нетермінальний символ). Формально має виконуватись: ${\displaystyle \alpha \in N,\beta \in (N\cup T)^{*}}$, де ${\displaystyle |\beta |\geq 1}$.

Розширенням КВ-граматик є стохастичні КВ-граматики. Правилам виведення співставляють ймовірність використання: ${\displaystyle \rho :P\rightarrow \mathbb {R} }$ де ${\displaystyle \sum _{p_{r}\in P_{r}}\rho (p_{r})=1}$

Для КВ-граматик визначено різні нормальні форми. В нормальних формах Чомскі (НФЧ) скорочуюють праву частину правил виводу, тобто права частина може складатись або з одного термінального символу, або з двох нетермінальних. Якщо в лівій частині міститься початковий символ, права частина може породжувати порожнє слово. Існує алгоритм, який переводить довільну КВ-граматику в НФЧ.

Контекстно-вільна граматика визначена в нормальній формі Грейбах (НФГ), якщо вона не породжує порожнього слова та права частина правил виводу починається з щонайбільше одного термінального символу, слідом за яким йдуть нетермінальні символи. Кожна КВ-граматика, яка не породжує порожнє слово, може бути перетворена в НФГ алгоритмом.

Контекстно-вільні граматики породжують контекстно-вільні мови, тобто кожна КВ-граматика породжує КВ-мову, і для кожної КВ-мови існує КВ-граматика, що її породжує.

Контекстно-вільну мову ${\displaystyle L}$, породжену КВ- граматикою ${\displaystyle G}$, позначають ${\displaystyle L(G)}$, де:

${\displaystyle L(G)=\{w|w\in T^{*},S\rightarrow _{G}^{*}w\}}$

Символом ${\displaystyle \rightarrow _{G}^{*}}$ позначають послідовність правил виводу граматики ${\displaystyle G}$, унаслідок застосування якої отримують слово ${\displaystyle w}$ мови ${\displaystyle L(G)}$. Також ${\displaystyle L(G)\subset T^{*}}$.

Контекстно-вільні мови можна розпізнати недетермінованим автоматом з магазинною пам'яттю. Якщо існує детермінований автомат, здатний розпізнати мову, її називають детермінованою КВ-мовою. Ця підмножина КВ-мов утворює теоретичну основу для синтаксиса багатьох мов програмування.

Контекстно-вільні мови можуть містити порожнє слово, наприклад, через правило виводу ${\displaystyle (S\rightarrow \varepsilon )}$.

Нехай ${\displaystyle G=(N,T,P,S)}$ — КВ-граматика

${\displaystyle T=\{x,y,z\}}$

${\displaystyle N=\{S,A,B\}}$

${\displaystyle P}$ складається з чотирьох правил виводу:

${\displaystyle {\begin{aligned}S&\rightarrow &A\\A&\rightarrow &xAy\\A&\rightarrow &xBy\\B&\rightarrow &z\end{aligned}}}$

${\displaystyle w_{1}=xxzyy}$ в граматиці ${\displaystyle G}$ можна отримати такою послідовністю застосування правил виводу:

${\displaystyle t(w_{1})=S(A(x,A(x,B(z),y),y))}$

, тут ${\displaystyle t(w_{1})}$ — дерево виведення. Корінь дерева та проміжні вузли позначені нетермінальними символами, а листи дерева позначені термінальними символами.

Таким чином, ${\displaystyle w_{1}\in L(G)}$.

Слово ${\displaystyle w_{2}}$ де ${\displaystyle w_{2}=z}$ не належить до мови ${\displaystyle L(G)}$, оскільки нетермінальний символ ${\displaystyle B}$ не початковий, а всі слова утворені від початкового мають розташовуватися посеред термінальних ${\displaystyle x}$ та ${\displaystyle y}$. Формально це записують:

${\displaystyle w_{2}\notin L(G)}$

Граматика ${\displaystyle G}$ не багатозначна.

• Нотація Бекуса — Наура
• Нормальна форма Чомскі

• Uwe Schöning. Theoretische Informatik - kurzgefasst. — 4. — Spektrum Akademischer Verlag, 2001. — С. 13, 51. — ISBN 3-8274-1099-1.