Малюнок 2.7. Програма як діалектичне заперечення проблеми 12 страница

Умова неперервності фактично говорить, що R=È_iÎwj(R⁽ⁱ⁾) є розв’язком рівняння S={e}È{a}S{b}. Дійсно, для iÎw маємо, що j(R⁽ⁱ⁾)=R⁽ⁱ⁺¹⁾, тому È_iÎw j(R⁽ⁱ⁾)=È_iÎw R⁽ⁱ⁺¹⁾=È_iÎw R⁽ⁱ⁾. Остання рівність випливає з того, що R⁽⁰⁾= Æ, тому маємо, що R=j(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®e (тоді гіпотеза справедлива), або з виводів довжини не більш ніж k після застосування правила S®aSb. В цьому випадку, всі породжені ланцюжки будуть належати R^(k+1). І навпаки, якщо ланцюжок належить R^(k+1), то він виводиться не більш ніж за k+1 крок._▄

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

Виникає питання, чи завжди розв’язок має бути єдиним. Рівняння S=SS є прикладом того, що це не так, бо воно має безліч розв’язків. Наприклад, його розв’язками є такі мови: S=Æ, S={e}, 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. Побудуйте граматику без e–правил, еквівалентну даній

          S→ABC

          A→BBçe

          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.  Для вищенаведених мов побудуйте відповідні автомати, які розпізнають ці мови.

 

 

5. Теорія рекурсії (теорія найменшої нерухомої точки)

5.1 Рекурсивні визначення та рекурсивні рівняння

 

Рекурсивні визначення – це такі визначення, в правій частині яких використовується посилання на поняття, що визначається. Такі визначення мають вид

.

Рекурсивне визначення можна тлумачити

· операційно, тобто вказати алгоритм, за яким можна обчислити рекурсивно визначений об’єкт,

· або денотаційно, тобто як рівняння, розв’язком якого є нерухомі точки (НТ) оператора j .

Зауваження 5. 1 Тут на j (x) ми дивимось синкретично (не розрізнюючи різні аспекти), та тлумачимо j (x) або як вираз в певній алгебрі (коли говоримо про рівняння), або як оператор в цій алгебрі (коли говоримо про нерухомі точки оператора).

Зауваження 5. 2 Часто також розглядаються системи рівнянь виду

Такі системи зводяться до одного рівняння над послідовністю (x ₁, x ₂, . . . , x _n).

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

Припустимо, що ми хочемо визначити суму 2+2²+2³+2⁴+... . Позначимо цю суму через x, тобто x=2+2²+2³+2⁴+... . Якщо винести 2 з усіх членів суми, крім першого члена, отримаємо наступне рекурсивне визначення: x=2+2x. Звідси x = –2, що зовсім не відповідає очікуванню.

Рекурсія може бути прихованою (неявною). Для ілюстрації розглянемо парадокс Рассела з теорії множин. А саме, множина x називається нормальною, якщо x Ï x. Позначимо через N множину усіх нормальних множин, тобто N ={ x | x Ï x}. Парадокс виявляється, якщо запитати, чи є N нормальною множиною? Отримуємо, що N Î N тоді і тільки тоді, коли N Ï N. Тут рекурсія виступає неявно, бо в визначенні N (неявно) припускається, що N може бути елементом N.

Наведені приклади говорять про необхідність детального вивчення рекурсії, щоб уникнути некоректностей та парадоксів.

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

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

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

Береться початкове наближення d ₀. Далі обчислюється послідовність наближень

За результат береться границя обчисленої послідовності: .

Зауваження 5. 3 В теорії найменших нерухомих точок зазвичай використовується позначення виду iÎw, де w – перший нескінченний ординал, тобто w={0, 1, 2, . . .} – множина натуральних чисел.

Метод послідовних наближень графічно представлений на малюнку 5.1. Наближення  мають границю d, яка є коренем рівняння .

 

Малюнок 5.1 Розв’язок рівнянь методом послідовних наближень

5.2 Частково впорядковані множини, границі ланцюгів та -області

Для того, щоб метод послідовних наближень міг бути застосований, необхідно задати відношення “наближеності” (це – частковий порядок), початкове наближення (у нашому випадку це буде найменший елемент), та гарантувати існування границі (повнота).

Вказані поняття можна формалізувати наступним чином.

Визначення 5 .1  

Множина D з заданим бінарним відношенням £ Í D´D називається частково впорядкованою множиною  (ЧВМ), якщо для відношення £ виконуються наступні аксіоми часткового порядку (d, d ₁,d ₂,d ₃ÎD):

1. Рефлексивність: ,
2. Транзитивність: ,
3. Антисиметричність: .

Визначення 5.2 Нехай  – ЧВМ,  – індексована підмножина D. Ця підмножина – ланцюг, якщо .

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

Визначення 5 .3 Нехай – ланцюг в ЧВМ . Границею X (позначається lim X = sup X = X = ) називається точна верхня границя (супремум, найменша мажоранта) множини X, якщо вона існує.

В теорії рекурсії зазвичай використовується позначення , або _iÎwd_i , або {d_i | iÎw}, або X. Останнім позначенням і будемо користуватися у подальшому.

Визначення 5 .4 ЧВМ  – повна, якщо для довільного ланцюга  з D існує його границя (що належить D).

---

Дата добавления: 2019-02-13; просмотров: 272; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!