Формальні граматики

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Формальна граматика або просто граматика в теорії формальних мов — спосіб опису формальної мови, тобто виділення деякої підмножини з множини всіх слів деякого скінченного алфавіту. Розрізняють породжувальні і аналітичні граматики — перші ставлять правила, за допомогою яких можна побудувати будь-яке слово мови, а другі дозволяють по даному слову визначити, входить воно в мову чи ні. Формальні граматики були введені американським вченим, математиком та філософом, Н. Хомським у 50-тих роках XX сторіччя.

Поняття алфавіту[ред. | ред. код]

Алфавіт — скінченна множина символів. ε — порожній ланцюжок, слово, послідовність. Алфавітом є об'єднання алфавітів, перетин, різниця алфавітів. Нехай Т — алфавіт, тоді:

  • Т+ — множина усіх можливих послідовностей, що складені з елементів цього алфавіту крім порожньої послідовності ε.
  • Т* — множина усіх можливих послідовностей, що складені з елементів цього алфавіту, будь-якої довжини. Отже:
  • Тk — множина усіх можливих послідовностей,що складені з елементів цього алфавіту, довжини не більше k.

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

Формальна граматика[ред. | ред. код]

Формальна граматика - це четвірка . Де:

  • Т — алфавіт термінальних символів, терміналів (від англ. terminate - завершитись). Термінальні символи є алфавітом мови.
  • N — алфавіт нетермінальних символів, нетерміналів. ; Нетермінали не входять в алфавіт мови.
  • S — аксіома, спеціально виділений нетермінальний символ з якого починається опис граматики.
  • P — правила виводу, скінченна підмножина множини .

Інколи P визначають так:. Елемент (α,β) з множини Р називається правилом виводу і записується у вигляді . Таким чином, ліва частина правила не може бути порожньою. Правила з однаковою лівою частиною записують: , - називаються альтернативами правила виводу з ланцюжка .

Виведення в формальних граматиках[ред. | ред. код]

Ланцюжок назвемо безпосередньо виведеним з ланцюжка в граматиці (позначається ), якщо .

Ланцюжок назвемо виведеним з ланцюжка в граматиці (позначається ), якщо

Термінальний рядок називається правильним(або сентенціальною формою) відносно граматики G якщо він виводиться з аксіоми цієї граматики.

Неоднозначності, та стратегії виводу[ред. | ред. код]

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

Приклад. Розглянемо таку граматику G = <N, Σ, P, S> зі схемою Р.

S → S +S |S *S |a

Покажемо, що для ланцюжка ω = a + a + a існує щонайменше два варіанти виводу:

  1. S ⇒ S + S ⇒ S + S + S ⇒ a + S + S ⇒ a + a + S ⇒ a + a + a
  2. S ⇒ S + S ⇒ a + S ⇒ a + S + S ⇒ a + a + S ⇒ a + a + a

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

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

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

Формальні мови[ред. | ред. код]

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

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

  • Граматики G1 та G2 називаються еквівалентними, якщо .
  • Граматики G1 та G2 називаються майже еквівалентними, якщо , тобто мови, ними породжувані, відрізняються не більш ніж на ε.

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

Класифікація граматик[ред. | ред. код]

Хомський також запропонував класифікацію граматик. Він виділив чотири типи граматик.

Класифікація за Хомським[ред. | ред. код]

Докладніше: Ієрархія Чомскі
Граматики Типу 0. Необмежені
це найзагальніший клас граматик. На правила не накладаються ніяких обмежень, окрім зазначених у визначенні. Вони еквівалентні Машині Тюринга. Доведено існування мов, які породжуються граматиками типу 0, але не граматиками типу 1, але невідомі прості приклади таких мов. Клас мов що породжуються необмеженою граматикою називається рекурсивно перелічними[en].
Граматики Типу 1
нескорочуюча або контекстно-залежна(КЗ) граматика. Вибір означення не впливає на множину мов, породжуваних граматиками цього класу, оскільки доведено, що множина мов, породжуваних граматиками, що не укорочують, збігається із множиною мов, породжуваних КЗ-граматиками.
  • Нескорочуючі граматики. Всі правила мають вигляд
    де означає кількість символів у рядку .
  • Контекстно-залежні граматики. Всі правила мають вигляд:
Граматики Типу 2. Контекстно-вільні граматики(КВ)
Всі правила мають вигляд
Тобто в усіх правилах цього виду зліва стоїть тільки один нетермінал. Тому вони і контекстно вільні, бо на використання правила для даного нетерміналу не впливають символи, що оточують його. Ці символи називають контекстом.
Граматики Типу 3. Регулярні граматики. А-граматики
можна визначити як праволінійну або ліволінійну граматику, або як змішану. Також ці мови називають скінченно-автоматними, бо вони еквівалентні скінченним автоматам, тобто клас мов, що породжуються граматиками типу 3, збігається з класом мов, які розпізнаються скінченими автоматами. Також ці граматики є основою регулярних виразів.
  • Праволінійна граматика. Всі правила мають вигляд:
    або
  • Ліволінійна граматика. Всі правила мають вигляд:
    або

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

Співвідношення між типами граматик[ред. | ред. код]

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

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

Співвідношення між типами мов[ред. | ред. код]

  1. кожна регулярна мова є КВ-мовою, але існують КВ- мови, що не є регулярними (наприклад, );
  2. кожна КВ- мова є КЗ- мовою, але існують КЗ-мови, що не є КВ-мовами ( наприклад, );
  3. кожна КЗ-мова є мовою типу 0.

Варто підкреслити, що якщо мова задана граматикою типу k, то це не означає, що не існує граматики типу k' (k'>k), що описує ту ж мову. Тому, коли говорять про мову типу k, звичайно мають на увазі максимально можливе k.

Використання формальних граматик[ред. | ред. код]

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

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

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]