Перегляд вихідного коду сторінки Формальна граматика

'''Формальна граматика''' або просто '''граматика''' в теорії [[формальна мова|формальних мов]] — спосіб опису формальної мови, тобто виділення деякої підмножини з множини всіх слів деякого скінченного [[Алфавіт (математика)|алфавіту]]. Розрізняють '' породжувальні '' і '' аналітичні '' граматики — перші ставлять правила, за допомогою яких можна побудувати будь-яке слово мови, а другі дозволяють по даному слову визначити, входить воно в мову чи ні. Формальні граматики були введені американським вченим, математиком та філософом [[Ноам Чомскі|Ноамом Чомскі]] у 50-тих роках 20 сторіччя. 

== Формальне визначення поняття ==
=== Поняття алфавіту ===
'''Алфавіт''' — [[скінченна множина]] символів.
''ε'' — порожній ланцюжок, слово, послідовність.
Алфавітом є об'єднання алфавітів, перетин, різниця алфавітів.
Нехай Т — алфавіт, тоді:
* Т<sup>+</sup> — множина усіх можливих послідовностей, що складені з елементів цього алфавіту крім порожньої послідовності ''ε''.
* Т* — множина усіх можливих послідовностей, що складені з елементів цього алфавіту, будь-якої довжини. Отже: <math>T^* =  T^+ \cup \{ \varepsilon \}</math>
* Т<sup>k</sup> — множина усіх можливих послідовностей,що складені з елементів цього алфавіту, довжини не більше k.

'''Мова''' в алфавіті Т це множина ланцюжків скінченної довжини в цьому алфавіті. Зрозуміло, що кожна мова в алфавіті Т є підмножиною множини Т*.

=== Формальна граматика ===
'''Формальна граматика''' - це [[Кортеж (інформатика)|четвірка]] (кортеж) <math>\boldsymbol{G = \{N,T,P,S\}}</math>. Де:
* '''Т''' — алфавіт термінальних символів, терміналів (від англ. terminate - завершитись). Термінальні символи є алфавітом мови.
* '''N''' — алфавіт нетермінальних символів, нетерміналів. <math>T \cap N = \empty</math>; Нетермінали не входять в алфавіт мови.
{{Falseredirect|Термінальні та нетермінальні символи}}
* '''S''' — аксіома, спеціально виділений нетермінальний символ з якого починається опис граматики.
:<math>\mbox{S}\in\mbox{N}</math>
* '''P''' — правила виводу, скінченна підмножина множини <math>(T \cup N)^+ \times(T \cup N)^*</math>.

Інколи '''P''' визначають так:<math>\alpha \in (T \cup N)^*\times N \times(T \cup N)^*, \beta \in (T \cup N)^* </math>.
Елемент (α,β) з множини Р називається ''правилом виводу'' і записується у вигляді <math>\alpha \to \beta</math>. Таким чином, ліва частина правила не може бути порожньою. Правила з однаковою лівою частиною записують: <math>\alpha \to \beta_1 \mid \beta_2 \mid ...\mid \beta_n</math>, <math> \beta_i \mbox{, i = 1,2,..,n} </math> - називаються альтернативами правила виводу з ланцюжка <math>\alpha</math>.

== Виведення в формальних граматиках ==
Ланцюжок <math>\beta \in (T \cup N)^*</math> назвемо '''безпосередньо виведеним''' з ланцюжка <math>\alpha \in (T \cup N)^+</math> в граматиці <math>G = \{T,N,S,P\}</math> (позначається <math> \alpha \Rightarrow \beta</math>), якщо <math>\alpha = \xi_1 \gamma \xi_2 , \beta = \xi_1 \delta \xi_2:  \xi_1 ,\xi_2 , \delta \in (T \cup N)^* , \gamma \in (T \cup N)^+ , \gamma \to \delta \in P</math>.

Ланцюжок <math>\beta \in (T \cup N)^*</math> назвемо '''виведеним''' з ланцюжка <math>\alpha \in (T \cup N)^+</math> в граматиці <math>G = \{T,N,S,P\}</math> (позначається <math> \alpha \Rightarrow^* \beta</math>), якщо 
:<math>\exists \gamma_0,\gamma_1,...,\gamma_n, n\ge 0 : \alpha = \gamma_0 \Rightarrow \gamma_1 \Rightarrow ...\Rightarrow \gamma_n = \beta</math>
 
Термінальний рядок називається '''правильним''' (або сентенціальною формою) відносно граматики G, якщо він виводиться з аксіоми цієї граматики.

== Неоднозначності, та стратегії виводу ==
Граматика G називається '''неоднозначною''', якщо існує декілька варіантів виводу слова ω в G ( ω ∈ L(G ) ).

'''Приклад.''' Розглянемо таку граматику G = <N, Σ, P, S> зі схемою Р.
 S → S +S |S *S |a
Покажемо, що для ланцюжка ω = a + a + a існує щонайменше два варіанти виводу:
# <pre>S ⇒ S + S ⇒ S + S + S ⇒ a + S + S ⇒ a + a + S ⇒ a + a + a</pre>
# <pre>S ⇒ S + S ⇒ a + S ⇒ a + S + S ⇒ a + a + S ⇒ a + a + a</pre>

В теорії граматик розглядається декілька стратегій виведення ланцюжка ω в G.

'''Лівостороння стратегія виводу''' ланцюжка ω в G — це послідовність кроків безпосереднього виводу, при якій на кожному кроку до уваги береться перший зліва направо нетермінал. 

'''Правостороння стратегія виводу''' ω в G протилежна лівосторонній стратегії. З виводом ω в G пов'язане [[абстрактне синтаксичне дерево]], яке визначає синтаксичну структуру програми.

== Формальні мови ==
[[Формальна мова]] породжена граматикою G - це множина термінальних рядків, що виводяться з аксіоми, тобто множина усіх правильних рядків. 
:<math>L(G) = \{\alpha \in T^*\mid S \Rightarrow^* \alpha \} </math>

З іншого боку, множина термінальних рядків, таких, що вони можуть бути виведені в граматиці G, називається мовою, що може бути розпізнана в даній граматиці, або допускається даною граматикою. 

* Граматики G<sub>1</sub> та G<sub>2</sub> називаються '''еквівалентними''', якщо <math>L(G_1) = L(G_2)</math>.
* Граматики G<sub>1</sub> та G<sub>2</sub> називаються '''майже еквівалентними''', якщо <math>L(G_1) \cup \{\varepsilon\} = L(G_2) \cup \{\varepsilon\}</math>, тобто мови, ними породжувані, відрізняються не більш ніж на ε.

Граматика може бути '''породжуючою''' та '''розпізнавальною''', це залежить від "напрямку" застосування правил. Для породжуючих граматик виведення починається з аксіоми і закінчується термінальним рядком (рядком, що складається тільки з терміналів). А розпізнавальні аналізують вхідний термінальний рядок на правильність, чи можна такий рядок вивести в цій граматиці. Коротко кажучи - породжуючі це "згори вниз", а розпізнавальні - "знизу вгору".
Остання задача є практичнішою і гострою.

== Класифікація граматик ==
[[Ноам Чомскі|Чомскі]] також запропонував класифікацію граматик. Він виділив чотири типи граматик.

=== Класифікація за Чомскі ===
{{Main|Ієрархія Чомскі}}

*Граматики Типу 0&nbsp;— необмежені. Це найзагальніший клас граматик. На правила не накладаються ніяких обмежень, окрім зазначених у визначенні. Вони еквівалентні [[Машина Тюрінга|машині Тюрінґа]]. Доведено існування мов, які породжуються граматиками типу 0, але не граматиками типу 1, але невідомі прості приклади таких мов. Клас мов що породжуються необмеженою граматикою називається {{iw|рекурсивно перелічна мова|рекурсивно перелічними||Recursively enumerable language}}. 
*Граматики Типу 1&nbsp;— нескорочуючі або контекстно-залежні(КЗ) граматики. Вибір означення не впливає на множину мов, породжуваних граматиками цього класу, оскільки доведено, що множина мов, породжуваних граматиками, що не укорочують, збігається із множиною мов, породжуваних КЗ-граматиками.
:* ''Нескорочуючі граматики''. Всі правила мають вигляд
:*: <math>\alpha\to\beta</math>
:*: <math>\alpha \in (T \cup N)^+, \beta \in (T \cup N)^* </math>
:*: <math>|\alpha|\le |\beta|</math>
:*: де <math>|\alpha|</math> означає кількість символів у рядку <math>\alpha</math>.
:* ''Контекстно-залежні граматики''. Всі правила мають вигляд:
:*: <math>\alpha\to\beta</math>
:*: <math>\alpha = \xi_1A\xi_2, \beta = \xi_1\gamma\xi_2: A \in N, \gamma \in (T \cup N)^+, \xi_1,\xi_2 \in (T \cup N)^*  </math>
*Граматики Типу 2&nbsp;— [[Контекстно-вільна граматика|контекстно-вільні граматики]](КВ): Всі правила мають вигляд
:<math>\alpha\to\beta</math>
:<math>\alpha \in N, \beta \in (T \cup N)^* </math>
:Тобто в усіх правилах цього виду зліва стоїть тільки один нетермінал. Тому вони і контекстно вільні, бо на використання правила для даного нетерміналу не впливають символи, що оточують його. Ці символи називають '''контекстом'''.
*Граматики Типу 3&nbsp;— регулярні граматики. А-граматики: можна визначити як праволінійну або ліволінійну граматику, або як змішану. Також ці мови називають скінченно-автоматними, бо вони еквівалентні [[Скінченний автомат|скінченним автоматам]], тобто клас мов, що породжуються граматиками типу 3, збігається з класом мов, які розпізнаються скінченими автоматами. Також ці граматики є основою [[Регулярний вираз|регулярних виразів]].
:* Праволінійна граматика. Всі правила мають вигляд:
:*: <math>\alpha\to\beta</math>
:*: <math>\alpha \to \omega\beta, \beta\in N, \omega \in T^*</math>
:*: або
:*: <math>\alpha \to \omega, \omega \in T^*</math>
:* Ліволінійна граматика. Всі правила мають вигляд:
:*: <math>\alpha\to\beta</math>
:*: <math>\alpha \to \beta\omega, \beta\in N, \omega \in T^*</math>
:*: або
:*: <math>\alpha \to \omega, \omega \in T^*</math>

Доведено, що праволінійні та ліволінійні граматики еквівалентні, і існує алгоритм для переведення правил граматики одного типу в інший тип.

=== Співвідношення між типами граматик ===
# Будь-які граматики типу 3 є граматиками типу 2.
# Будь-які КВ-граматики є граматиками типу 1 (КЗ або неукорочуючі), з точністю до ε.
# Будь-які граматики типу 1 є граматиками типу 0.

Мова L(G) є ''мовою типу k'', якщо її можна описати граматикою типу ''k''.

=== Співвідношення між типами мов ===
# кожна регулярна мова є КВ-мовою, але існують КВ- мови, що не є регулярними (наприклад, <math>L = \{a^nb^n \mid n>0\}</math>);
# кожна КВ- мова є КЗ- мовою, але існують КЗ-мови, що не є КВ-мовами ( наприклад, <math>L = \{a^nb^nc^n \mid n>0\}</math>);
# кожна КЗ-мова є мовою типу 0.
Варто підкреслити, що якщо мова задана граматикою типу k, то це не означає, що не існує граматики типу k' (k'>k), що описує ту ж мову. Тому, коли говорять про мову типу k, звичайно мають на увазі максимально можливе k.

== Використання формальних граматик ==
Формальні граматики -  це дуже потужний математичний інструмент, який використовується в математичній та комп'ютерній лінгвістиці, описі [[Мова програмування|мов програмування]], розробці компіляторів в теорії програмування. Найбільш вживаними є КВ-граматики і регулярні, бо їх найлегше описати алгоритмічно.

Сама по собі концепція формальних граматик доволі гнучка, тому не дивно, що з'явилося багато інших інструментів, що розширюють використання та потужність КВ-граматик і граматик третього типу. Наприклад, [[атрибутні граматики]], [[LL-k граматики]], [[Скінченний автомат|скінченні автомати]], [[Регулярний вираз|регулярні вирази]] та [[регулярні множини|множини]].

== Див. також ==
{{Портал|Математика}}
* [[Нотація Бекуса — Наура]]
* [[Синтаксичний аналіз]]
* [[Ієрархія Чомскі]]

== Література ==
; Українською
* {{ref-uk}} {{книга
|автор        = [[Гаврилків Володимир Михайлович|Гаврилків В. М.]]
|назва        = Формальні мови та алгоритмічні моделі
|рік          = 2023
|видавництво  = Голіней
|місто        = {{Comment|І.-Ф. |Івано-Франківськ}}
|сторінок     = 180
}}

; Іншими мовами
* ''Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.'' [https://web.archive.org/web/20100128063740/http://trpl.narod.ru/TRYAP_BOOK_Details.htm Теория и реализация языков программирования] //М.: МЗ-Пресс, 2006 г., 2-е изд. ISBN 94073-094-9. {{ref-ru}}

{{Math-stub}}
{{Comp-sci-stub}}
{{додаткові джерела|дата=квітень 2008}}
{{ВП-портали|Програмування|Математика}}

{{Математична логіка|state=collapsed}}

[[Категорія:Формальні мови|*]]
[[Категорія:Математична логіка]]