Лекція №8 основи теорії формальних граматик Основні поняття граматик

За останні десять років з'явилася велика кількість робіт із загальної теорії мов і граматик.

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

Перше із цих напрямків пов'язане з побудовою формальної або математичної лінгвістики. Виникнувши спочатку у зв'язку з формальним вивченням структури літературної мови, математична лінгвістика почала особливо швидко розвиватися, коли були сформульовані, наприклад, такі питання машинного перекладу: чи всяка фраза може бути переведена з однієї мови на іншу при заданому запасі правил у пам'яті машини; як описати множину текстів, доступних для перекладу при заданих умовах. Спроба не тільки відповісти, але навіть точно поставити питання такого роду відразу ж вимагали формалізації понять «словник», «граматика», «мова», підрозділи й класифікації цих понять й уміння відносити конкретні словники, граматики, мови до того або іншого класу. Це послужило стимулом для великої кількості робіт, що досліджують зазначені поняття з позицій формальної лінгвістики.

Поява штучних машинних мов програмування ще більше підсилила інтерес до задач такого роду. Однак прийнятий раніше в лінгвістиці винахідницький (евристичний) підхід до нових мов, при якому оцінка зручності мови була справою інтуїції й досвіду, виявився явно недостатнім для машинних мов. Положення збільшилося появою трансляторів, які зробили проблему перекладу центральної, багато в чому визначальну побудову загальної теорії обчислювальних машин. Самі ж машинні мови стали усе більше наближатися до формально побудованих математичних конструкцій.

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

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

Це породило численні спроби побудувати проміжні моделі динамічних систем, більше широкі, чим скінченний автомат, але більше вузькі, чим машини Т'юрінга, і або класифікувати ці моделі. Був очевидний глибокий зв'язок всіх цих питань із теорією алгоритмів. Сама ж постановка питання йшла не від математичної абстракції «алгоритм», а скоріше від механічного формалізму «динамічна система».

Незалежно й паралельно розвивалася загальна теорія алгоритмів як галузь сучасної математики. Була встановлена еквівалентність понять «нормальний алгоритм Маркова», «загальрекурсивна функція» й «машина Т'юрінга», а теза Черча зв'язав ці три поняття з інтуїтивним поданням про алгоритм. Розвиток обчислювальної техніки поставило перед математичною теорією алгоритмів нову задачу: стало необхідно класифікувати алгоритми, наприклад, по обчислювальній складності. Еквівалентність понять «алгоритм» й «машина Т'юрінга» зробила природним припущення про те, що пошуки класифікації алгоритмів виявляться у відомій мері пов'язаними з пошуками проміжних моделей між моделями скінченного автомата й машиною Т'юрінга.

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

Теорія формальних граматик і мов є основним розділом математичної лінгвістик-специфічної математичної дисципліни, орієнтованої на вивчення структури природних і штучних Мов.

Ця теорія виникла в 50-і роки в роботах американського лінгвіста Н. Хомского(хоча основи апарата, на якому вона базується, були розроблені в математичній лінгвістиці значно раніше). При цьому Хомский виходив винятково з потреб лінгвістики, за традицією, що розуміє як наука про будову природних мов. Однак дуже незабаром виявилося, що методи його теорії в не меншому ступені застосовні до штучних спеціалізованих мов, і зокрема до алгоритмічного. Це порозумівається тим, що алгоритмічні мови простіше влаштовані й краще піддаються формалізації, чим природні мови.

По характері використовуваного математичного апарата теорія формальних граматик і мов близька до теорії алгоритмів і до теорії автоматів.

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

Ці ланцюжки можуть інтерпретуватися як язикові об'єкти різних рівнянь, наприклад як словоформи, словосполучення й пропозиції.

Словоформа або проста слово - (послідовність) ланцюжок морфем (морф). Морфем--дрібна граматично значима частина слова (словоформи).

Так, наприклад, словоформа ведший складається з морфем вед + + ш + ий (+ — границя морфем). Де вед — корінь, ш — суфікс, ий— закінчення.

Словосполучення й пропозиція - ланцюжок словоформ.

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

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

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

Структурний опис буде тоді й тільки тоді однозначно, коли в мові через граматику однозначно визначені його синтаксичні одиниці й ієрархічний взаємозв'язок між ними.

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

Формальні граматики мають справу з абстракціями, що виникають шляхом узагальнення понять словоформа, словосполучення, пропозиція.

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

Між звичайними й формальними граматиками є істотне розходження. У формальних граматиках всі твердження формулюються в термінах невеликого числа чітко певних і досить елементарних символів й операцій. Це робить формальні граматики порівняно простими з погляду їхньої логічної будови й полегшує вивчення їхніх властивостей.

Однак формальні граматики виявляються досить громіздкими для опису природної мови й тому призначаються сугубо для наукового, теоретичного дослідження найбільш загальних властивостей мови.

Розрізняють що розпізнають, що породжують і перетворять формальні граматики.

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

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

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

Розглянемо клас граматик, що породжують. граматикою, Що Породжує, будемо називати впорядковану систему G = (VT, VH, Р, S) , де VT - скінченна не порожня множина символів, називана термінальним (основним) словником G.

Терминальний словник — набір вихідних елементів, з яких будуються ланцюжки, породжувані граматикою, або словник основних слів мови, з яких будуються пропозиції. V_H— скінченна непуста множина символів, називається нетермінальним (допоміжним) словником G.

Нетермінальний словник - набір символів, якими позначаються класи або ланцюжки вихідних елементів, або словник синтаксичних типів.

Елементи V_T й V_H називаються відповідно, термінальними або нетермінальними символами.

V =V_T U V_H — скінченна множина символів, називана словником граматики G. Довільну скінченну послідовність із елементів V будемо називати ланцюжком у словнику V. Порожній ланцюжок позначається Λ , у такий спосіб ωΛ= Λω = ω. Число членів цієї скінченної послідовності назвемо довжиною ланцюжка й будемо позначати |ω|.

Ланцюжка символів словника V виходять за допомогою операції

з'єднання (конкатенації) . Наприклад, ω = а1а2а3. Якщо не виникає неоднозначності, символ може опускатися. Операція з'єднання ассоціативна, але не коммутативна.

S — початковий символ. Це виділений нетермінальний символ, що позначає клас всіх тих язикових об'єктів, для опису яких призначається дана граматика. У літературі символ S називається ще аксіомою, або метою граматики.

Р — правила граматики або скінченна множина ланцюжків виду φ→ψ, де φ, ψ— слова в словнику V, і ланцюжок φ містить принаймні один символ зі словника V_H. Скінченне, двумісне відношення → інтерпретується як «замінити φ на ψ», або «поставити ψ замість φ». Це відношення має властивості асимметричности й иррефлексивності. Ланцюжка виду φ → ψ називаються правилами підстановки, або просто правилами граматики. А множина Р — схемою граматики.

Если задана грамматика G = (V_т, V_H, Р, S), то будем говорити:

1. Ланцюжок ω виходить (безпосередньо) з ланцюжка ω' застосуванням правила φ → ψ, якщо ω = ζ₁ψζ₂, ω' = ζ₁ψζ₂, і { φ → ψ } Р.

2. Послідовність ланцюжків φ = φ₀, φ₁, φ₂, … , φ_n = ψ(n≥1)

є φ — вивід ланцюжка ψ, якщо для кожного i φ _i+1 треба з φ_i,

де 0≤i≤n. Наявність φ виводу ланцюжка ψ будемо позначати φ = > ψ.

Кількість застосувань правил у даному виводу називається його довжиною. Довжина виводу дорівнює числу ланцюжків у ньому, не лічачи початкового символу.

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

4. Вивід ланцюжка ψ уважається закінченим, якщо не існує ланцюжка, яка виходить з ψ.

5. Ланцюжок, що складається тільки з термінальних символів, називається термінальним ланцюжком (кожен термінальний ланцюжок є ланцюжки в словнику V_т, і до жодного із символів V_т не застосовне жодне із правил граматики G).

Множина ланцюжків, виведених у граматиці G, називається мовою, породженою цією граматикою, і позначається L(G).

Мова L(G) називається термінальним, якщо L — множина термінальних ланцюжків граматики G.

Умовимося при написанні конкретних граматик, якщо це не обговорено особливо, першими рядковими латинськими буквами а, b, ... позначати елементи термінального словника V_т, елементи нетермінального словника V_H — прописними латинськими буквами А, В, ... а елементи загального словника V — рядковими грецькими буквами α, β, ... Речення, складені із цих символів, будемо позначати останніми буквами відповідних алфавітів, тобто х, в, ... — речення, складені з елементів термінального словника, X, Y, ... — пропозиції з елементів нетермінального словника, ω, φ , ψ, ... - пропозиції з елементів загального словника.

Далі, скрізь, якщо до позначення якої-небудь множини додана зверху зірочка, наприклад замість V написане V*, це означає, що мається на увазі множина всіх ланцюжків, які можуть бути отримані із символів множини V.

Розглянемо уведені поняття на прикладі.

Нехай задана граматика G = (V_т, V_н, Р, S), де

V_T={a, b};

V_н = {А, В, С};

S=C;

Р={С>аb, С>асb}.

Нехай

ω = аСb, ω' = ааСbb.

Ланцюжок ?' безпосередньо виводиться з ланцюжка ? у результаті застосування одного правила.

φ — вивід: аСb, ааСbb, аааСbbb, ааааbbbb. Останній ланцюжок є термінальною. Довжина виводу рівняється трьом.

З наведеного приклада видно, що граматика, що породжує, не є алгоритмом.

Правила підстановки це не послідовність приписань, а сукупність дозволів. Це означає:

1. Правило виду φ →ψ розуміється в граматиці як «φ можна замінити на ψ» (а можна й не заміняти), тоді як в алгоритмі воно означало б «φ варто замінити на ψ» (не можна не замінити).

2. Порядок застосування правил у граматиці довільний, тоді як в алгоритмі був би заданий жорсткий порядок застосування окремих інструкцій.

Дві грамматики-G₁ й G₂ — називаються слабко еквівалентними, якщо вони породжують той самий мову, L_G1 = L_G2 або дві граматики називаються слабко еквівалентними, якщо збігається множина породжуваних ними фраз.

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

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

У теорії Хомского виділяються й вивчаються чотири типи мов, породжуваних відповідно чотирма типами граматик. Ці граматики виділяються шляхом накладення послідовно, що підсилюються обмежень, на систему правил Р.

Граматика називається граматикою типу 0 у тих випадках, коли не накладається ніяких обмежень на правила φ →ψ, де φ і ψ можуть бути будь-якими ланцюжками зі словника V.

Граматика називається граматикою типу 1, якщо в системі Р правила φ →ψ задовольняють умові φ =

=φ₁A φ₂, ψ = φ₁ω φ₂, де А — нетермінальний символ, а ψ,φ,ω — ланцюжок зі словника V. Таким чином, у граматиках типу 1 окремий нетермінальний символ А переходить у непустий ланцюжок ω контексті φ₁ й φ₂ (φ₁ й φ₂ можуть бути порожніми ланцюжками). Граматики типу 1 називають контекстними граматиками.

Граматика називається граматикою типу 2—бесконтекстною, якщо в системі правил Р припустимі лише правила виду А→ω, де А — нетермінальний символ, а ω — непустий ланцюжок з V.

Відповідно до правил цієї граматики, заміна А на ω відбувається незалежно від контексту.

Граматика називається граматикою типу 3, коли припустимі лише правила виду А →ω,де ω = аВ, або ω = =а.

Уведені тут класи можуть бути розбиті на підкласи. Такий поділ буде розглянуто далі.

Вправи:

1. Нехай G = (V_т, V_H, Р, S) граматика, що-породжує, де Vт = {а, d, }}, Vн = {В, С, S}, Р= {S→ав, В→Сd, С→е}.

Виписати термінальні ланцюжки, породжувані даною граматикою, і визначити довжину їхнього висновку.

2. Нехай G = (V_т, V_н, Р, S), де V_т = {а, d, е), V_н = {В,С, S}, Р = {S→аВ, В→Сd, В→dС, С→е) . Визначити термінальні ланцюжки, породжувані даною граматикою, і довжину їхнього виводу.

3. Для граматики G відомий її загальний словник V = {А, В, С, D, Е} і схема правил Р= {E→DСВ, Е→А, D→ВР,D→С, А→ВВ). Визначити склад термінального й нетермінального словників, ціль граматики, побудувати мова L (G) і визначити довжину висновків для кожного термінального ланцюжка.

4. Визначити, чи є породжуючими наступні граматики:

a) G= ({А, В},{S, D},Р ={S→ AB, S→ASD, SD→B, В→AS}, S);

2. G= ({А, В}, {S}, P= {S→АSВА, S→AВ, АS→В}, S);

3. G= {{В, С), {А,S}, Р= {S→ А, А→В, A→СА}, S);

4. G = ({В,С), {А, S}, Р= {S→A, A→В, А→САС}, S).

5. Дано граматику G = (V_т, V_н, Р, S), де V_т = {А, В}, V_н = {S, D}, Р={S→AВ, S→ADSВ, D→ВSВ, DS→В, D→Λ}. Показати, що ланцюжок АВАВВАВ належить множині L (G).

6. Дано граматику G = ({а, b, з, d, е), {А, В, З, D Е), Р = {A→ed, В→Ab, З→Вс, С→d, D→аЕ, Е→bc}, З). Визначити, чи належить множині L(G) ланцюжок еаdаbсbс.

7. Дано V = {С, S, а, b} й V_т = {а, b}. Визначити, чи є граматикою четвірка (V_т, V_н, Р, S) для наступних множин правил граматики:

1. Р = {С→b, S→аСb};

2. Р= {b>а, С>Sb};

с) Р={С→bСаС, СS→Λ};

d) Р = {С→bС, СS→а, S→а}.

8. Нехай для кожного n ≥1G = ({а}, {S→Sⁿ}, S). Показати, що яке б не було п, L(G_n) = .

9. Задано термінальний словник граматики. Визначити граматики, що породжують наступні мови:

1. мова а^пb^па^п для n≥1;

2. мови для n?1;

3. мова а^п для п≥1.