0. 4.13 Розв’язні та нерозв’язні проблеми кв-граматик та мов

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

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

Для КВ-граматик та мов наступні проблеми є розв’язними:

1. Чи є мова, породжувана КВ-граматикою, порожньою?

2. Чи є мова, породжувана КВ-граматикою, скінченною?

3. Чи є мова, породжувана КВ-граматикою, нескінченною?

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

Для КВ-граматик та КВ-мов наступні проблеми є нерозв’язними.

1. Чи є перетин мов, породжуваних двома КВ-граматиками, порожнім?

2. Чи є перетин мов, породжуваних двома КВ-граматиками, скінченним?

3. Чи є перетин мов, породжуваних двома КВ-граматиками, нескінченним?

4. Чи є КВ-граматика однозначною?

5. Чи є порожнім (скінченним, нескінченним) доповнення до КВ-мови?

6. Чи співпадає КВ-мова, породжувана граматикою, з T*?

7. Чи є еквівалентними дві КВ-граматики?

8. Чи є регулярною мова, породжувана КВ-граматикою?

Зазначимо, що проблеми, розв’язні для КВ-граматик та мов будуть розв’язними і для регулярних граматик та мов. Разом з тим, деякі проблеми, нерозв’язні для КВ-граматик та мов, можуть бути розв’язними для регулярних граматик та мов. Зокрема, такими є вищенаведені проблеми 1-7, переформульовані на випадок регулярних граматик та мов.

0. 4.14 Рівняння в алгебрах формальних мов

Граматики та БНФ є формалізмами, що задають мову «поштучно», «поелементно», вказуючи механізм породження окремих слів. Разом з тим, сама форма граматик та БНФ підштовхує до думки, що їх можна розглядати як системи рівнянь, розв’язками яких є мови. Щоб перейти до такого тлумачення, попередньо введемо необхідні визначення.

Визначення 4.43 Слабкою алгеброю формальних мов над алфавітом T будемо називати алгебру AL=(2^T*, , ·) з операціями об’єднання та добутку мов.

Визначення 4.44 Множиною виразів LExp над множиною змінних Var називається множина, задана наступним індуктивним визначенням:

1. якщо x Var, то x Lexp,

2. якщо LT*, то LLexp,

3. якщо t, tLexp, то tt, t·tLexp.

Визначення 4.45 Формальним рівнянням (формальною рівністю) над алгеброю AL називається запис вигляду t=t, де t, tLexp.

Визначення 4.46 Інтерпретацією (означуванням, оцінкою) змінних називається довільне відображення : Var2^T*. Інтерпретація змінних однозначно (та гомоморфно) продовжується до відображення _: LExp2^T* інтерпретації виразів, параметром якого є інтерпретація змінних , яке задається індуктивно за побудовою виразу eLexp:

1. якщо e =x (xVar), то _(e)= (x),

2. якщо e =L (L T*), то _(e)= L,

3. якщо e = tt, то _(e)=_(t)_(t),

4. якщо e = t·t, то _(e)=_(t) · _(t).

Визначення 4.47 Наведене визначення дозволяє абстрагувати відображення _ до оператора : LExp  ((Var2^T*)2^T*). Вираз e, який містить змінні x₁, …, x_n, будемо позначати e(x₁, …, x_n), а відповідний оператор – ( e(x₁, …, x_n)).

Приклад 4.29 Нехай Var = {x, y, z}, (x)={a,ab}, (y)={,b,cc}, (z)={bb,c}. Тоді вираз x²z{a}y інтерпретується таким чином:

_(x²z{a}y)={a,ab}²{bb,c}{a}{,b,cc}={aa, aab, aba, abab}{bba,ca}{,b,cc}=

{aabba, aabbba, ababba, ababbba, aaca, aabca, abaca, ababca}{,b,cc} =

{aabba, aabbba, ababba, ababbba, aaca, aabca, abaca, ababca, b,cc} =

{aabbab, aabbbab, ababbab, ababbbab, aacab, aabcab, abacab, ababcab, aabbacc, aabbbacc, ababbacc, ababbbacc, aacacc, aabcacc, abacacc, ababcacc}

Визначення 4.48 Інтерпретація (означування) змінних : Var2^T* називається розв’язком рівняння t=t, якщо _(t)=_(t).

Визначення 4.49 Розвязком системи рівнянь {t₁=t₁, …, t_n=t_n} є така інтерпретація змінних, яка кожне рівняння перетворює у рівність.

Визначення 4.50 Рівняння виду x=t, де xVar, tLexp називаєть рекурсивним. Якщо у виразі t фігурують лише скінченні мови, то рівняння називають слабкорекурсивним. Аналогічно вводяться понятя рекурсивних та слабко рекурсивних систем рівнянь.

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

Приклад 4.30

Розглянемо мову L={aⁿbⁿ | n0}. Ця мова породжується наступною простою граматикою G: S | aSb.

Цій граматиці відповідає наступне рівняння: S={}{a}S{b}. Позначимо оператор ({}{a}S{b}(S)) як (S).

Розв’язок рівняння знаходять методом послідовних наближень. Найперше наближення – порожня мова . Наступні наближення отримуємо підстановкою в оператор (S) замість S попереднього наближення. (Для спрощення тут можна говорити про підставку в саме рівняння). Отримуємо наступну послідовність наближень:

R⁽⁰⁾= ;

R⁽¹⁾= {};

R⁽²⁾= {}{ab}={, ab};

R⁽³⁾= {, ab}{ab, aabb}={, ab, aabb};

… … …

R⁽ⁱ⁺¹⁾=R⁽ⁱ⁾{a} R⁽ⁱ⁾{b};

… … …

Вважаємо, що

R=_i R⁽ⁱ⁾.

(Тут  є першим граничним ординаром і може тлумачитись як множина натуральних чисел. Детальніше про це буде сказано у наступному розділі посібника.)

Використовуючи оператор  отримуємо, що R⁽ⁱ⁺¹⁾=( R⁽ⁱ⁾) та R=_i(R⁽ⁱ⁾). Мова R і буде розв’язком нашого рівняння.

Щоб це довести, розглянемо наступну властивість оператора .

Лема 4.22 (неперевність ). (_i R⁽ⁱ⁾)= _i (R⁽ⁱ⁾).

Доведення.

Спочатку доведемо, що (_i R⁽ⁱ⁾)_i (R⁽ⁱ⁾). Дійсно, нехай x(_i R⁽ⁱ⁾). Тоді x{}, або x{a}(_i R⁽ⁱ⁾){b}. В першому випадку очевидно, що x_i (R⁽ⁱ⁾). У другому випадку x(R⁽ⁱ⁺¹⁾), тому x_i (R⁽ⁱ⁾).

Тепер доведемо, що (_i R⁽ⁱ⁾)_i (R⁽ⁱ⁾). Нехай тепер x_i (R⁽ⁱ⁾). Тоді існує k таке, що x(R^(k)). Це означає, що x{}, або x{a}(R^(k-1)){b}. Тому x{a}(_i R⁽ⁱ⁾){b}, тобто x(_i R⁽ⁱ⁾). _▄

Умова неперервності фактично говорить, що R=_i(R⁽ⁱ⁾) є розв’язком рівняння S={}{a}S{b}. Дійсно, для i маємо, що (R⁽ⁱ⁾)=R⁽ⁱ⁺¹⁾, тому _i (R⁽ⁱ⁾)=_i R⁽ⁱ⁺¹⁾=_i R⁽ⁱ⁾. Остання рівність випливає з того, що R⁽⁰⁾= , тому маємо, що R=(R).

Неважко довести, що цей розвязок співпадає з мовою, породженою граматикою G.

Лема 4.23 L(G)=R.

Доведення проводиться індукцією. Індуктивне твердження наступне: нехай L(G)^k – усі термінальні слова, що виводяться з S виводами довжини не більше k, тоді L(G)^k= R^(k).

База індукції. Для k=0 маємо L(G)⁰= R⁽⁰⁾= .

Крок індукції. Нехай індуктивна гіпотеза справедлива для довільного k. Доведемо її справедливість для k+1.

Дійсно, виводи довжини не більш ніж k+1 отримуємо або застосуванням правила S (тоді гіпотеза справедлива), або з виводів довжини не більш ніж k після застосування правила SaSb. В цьому випадку, всі породжені ланцюжки будуть належати R^(k+1). І навпаки, якщо ланцюжок належить R^(k+1), то він виводиться не більш ніж за k+1 крок._▄

У наведеному прикладі ми знайшли лише один розв’язок рівняння. Неважко довести, що цей розв’язок дійсно є єдиним. Доведення можна провести від супротивного, вибравши з іншого розв’язку R найменше за довжиною слово, що не належить R, тоді з рівняння має випливати існування ще меншого слова, що не належить R. Отримане протиріччя говорить про єдиність розв’язку. (Деталі доведення з’ясуйте самостійно.)

Виникає питання, чи завжди розв’язок має бути єдиним. Рівняння S=SS є прикладом того, що це не так, бо воно має безліч розв’язків. Наприклад, його розв’язками є такі мови: S=, S={}, S={a}*, S={aa}*, S={ab}*, S={aba}* і т.д.

Інші питання, пов’язані з розв’язком рекурсивних рівнянь, розглянемо у наступному розділі, присвяченому рекурсії.

Висновки

В цьому розділі були розглянуті основні методи подання синтаксису програм. Серед таких методів можна виділити методи породження та сприйняття мов. Формалізмами породження мов є породжуючі граматиками, сприйняття мов – автомати (машини). Синтаксис мов програмування звичайно подається формалізмами, які еквівалентні контекстно-вільним граматикам. В розділі визначено класифікацію граматик за Хомським, зв’язок класів граматик з класами автоматів, та проведено детальне дослідження класу контекстно-вільних граматик.

Основні результати цього розділу полягають у наступному:

1. Побудовано над-абстрактну та абстрактну моделі формальних мов як множин речень.

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

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

4. Наведено приклад доведень в теорії породжуючи граматик.

5. Наведено класифікацію класів граматик за Хомським.

6. Дано визначеня загально-контекстних граматик.

7. Наведено визначення різних формалізмі сприйняття мов.

8. Встановлено еквівалентність між класами граматик та відповідними класами автоматів (машин).

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

10. Розглянуто властивості контекстно-вільних граматик та мов.

11. Сформульовані розв’язні та нерозв’язні проблеми породжуючи граматик та мов.

12. Розглянуто рівняння в алгебрах мов.

Контрольні питання.

1. Дайте визначення синтаксичного аспекту програм.

2. Від яких аспектів програм абстрагуються при вивченні синтаксичного аспекту? Сформулюйте відповідний принцип.

3. Сформулюйте принцип, який вказує на співвідношення синтаксичного та семантичного аспектів?

4. Поясніть вживання терміну «формальна мова».

5. Обгрунтуйте принцип теоретико-множинного тлумачення формальних мов. Порівняйте цей принцип з теоретико-функціональним принципом формалізації програм.

6. Як визначається над-абстрактна модель формальної мови?

7. Як визначається абстрактна модель формальної мови? Проекціями яких категорій є ця модель?

8. Обгрунтуйте конкретизацію речень як послідовностей символів. Сформулюйте відповідний принцип.

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

10. Обгрунтуйте вибір транзиційної системи як дескриптивної моделі формальний мов. Сформулюйте відповідний принцип.

11. Обгрунтуйте необхідність подальної конкретизації транзиційних систем. У чому суть такої конкретизації?

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

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

14. Що таке вільна напівгрупа?

15. Що таке формальна мова?

16. Визначте теоретико-множинні операції над формальними мовами.

17. Що таке операція конкатенації (добутку) формальних мов?

18. Що таке операція ітерації формальних мов?

19. Що таке операція обернення формальної мови?

20. Що таке породжуючи граматика?

21. Дайте визначення відношення безпосередньої вивідності та його рефлексивного транзитивного замикання.

22. Дайте визначення виводу в граматиці.

23. Що таке словоформа (сентенційна форма)?

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

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

26. Визначте класи граматик за Хомським. Яке співвідношення цих класів?

27. Які граматики називаються загально-контекстними?

28. Як співвідносяться класи породжуючи та загально-контекстних граматик?

29. У чому полягає відмінність між механізмами породження та сприйняття мов?

30. Яку особливості вирізняють автомати від граматик?

31. Дайте визначення машини Тьюрінга. Вкажіть на інтенсіональні та екстенсіональні аспекти для формалізму машин Тьюрінга. Як визначається мова, яка розпізнається машиною Тьюрінга?

32. Як співвідносяться машини Тьюрінга та породжуючі граматики?

33. Дайте визначення лінійно-обмеженого автомата.

34. Як співвідносяться лінійно-обмежені автомати та породжуючі граматики?

35. Дайте визначення магазинного автомата.

36. Як співвідносяться магазинні автомати та породжуючі граматики?

37. Дайте визначення скінченного автомата.

38. Як співвідносяться скінченні автомати та породжуючі граматики?

39. Дайте визначення регулярної мови.

40. Як пов’язані регулярні мови з породжуючи ми граматиками та автоматами?

41. Які методи подання синтаксису використовуються для мов програмування?

42. Що таке нормальні форми Бекуса–Наура?

43. Які конструкції вживаються для модифікованих БНФ?

44. Що таке синтаксичні діаграми?

45. Як зв’язані БНФ, модифіковані БНФ, контекстно-вільні граматики та синтаксичні діаграми?

46. Сформулюйте основні властивості КВ-граматик.

47. Що таке продуктивні та досяжні нетермінали?

48. Яка граматика називається зведеною?

49. Дайте визначення різним нормальним формам КВ-граматик.

50. Що таке рекурсивний нетермінал?

51. Сформулюйте основні властивості КВ-мов.

52. Сформулюйте властивості замкненості КВ-мов відносно основних операцій.

53. Що таке дерево виводу в КВ-граматиці?

54. Які граматики називаються однозначними?

55. Які мови називаються суттєво неоднозначними?

56. Сформулюйте розв’язні проблеми КВ-мов та граматик.

57. Сформулюйте нерозв’язні проблеми КВ-мов та граматик.

58. Що таке алгебра мов?

59. Що таке рівняння в алгебрі мов?

60. Яким чином знаходяться розв’язки рівнянь в алгебра мов?

Вправи.

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

2. Побудувати породжуючу граматику G для мови L={aⁿb²ⁿcⁿ | n >0 }, довести, що L(G)=L, та що мова L не є КВ мовою.

3. Побудувати граматику G та систему рівнянь S для мови L={a²ⁿbⁿ | n >0 } та довести, що L(G)=L та R(S)=L.

4. Перетворіть граматику

S→AB

A→aBbSb

B→ABBa

B→ASb

на еквівалентну їй КВ-граматику, що не містить несуттєвих символів.

5. Побудуйте граматику без –правил, еквівалентну даній

S→ABC

A→BB

B→CCa

C→AAb

6. Побудуйте КВ-граматики, що породжують

а) усі ланцюжки з нулів та одиниць однаковою кількістю тих та інших;

б) всі можливі послідовності правильно розставлених дужок;

в) {a₁a₂…a_na_n…a₂a₁a_i{0, 1}, 1in};

г) {0ⁱ1 ^j ij, j0}.

7. Побудуйте ліволінійні граматики для мов, що складаються з

а) ідентифікаторів довільної довжини, які починаються з букви (як в Алголі);

б) ідентифікаторів довжиною від одного до шести символів, які починаються з букви I, J, K, L, M або N (як ідентифікатори цілих змінних в Фортрані);

в) усіх ланцюжків з нулів та одиниць, які мають парну кількість нулів та одиниць.

Опишіть мову, яка породжується правилами

8. Опишіть мову, яка породжується правилами

S→bSS

S→a

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

а) {a^n*nn1};

б) {ww{a, b, с} та кількість символів a в ланцюжку w рівна кількості символів b, рівна кількості символів c};

в) { ww w{a, b}};

г) {a^mbⁿa^mbⁿm1, n1}.

10. Для вищенаведених мов побудуйте відповідні автомати, які розпізнають ці мови.