Нормальна форма Хомського

Визначення 4.36 Назвемо КВ-граматику G=(N, T, P, S) граматикою у нормальній формі Хомсього, якщо її правила мають вигляд S→ ε, A→ a, A→ BC для деяких A, B, C∈ N, a∈ T.

Лема 4.7 За кожною КВ-граматикою можна побудувати еквівалентну їй граматику у нормальній формі Хомського.

Доведення. Нехай дана КВ-граматика G=(N, T, P, S). Проведемо ряд перетворень цієї граматики так, що породжувана нею мова залишиться незмінною. Спочатку побудуємо еквівалентну граматику G′ =(N′, T′, P′, S′) без ε -правил. Далі замінимо у всіх правилах кожен термінальний символ a на

новий нетермінальний символ N(a) і додамо до множини P правила

N(a)→ a для всіх a∈ T.

Видалимо правила вигляду A→ A1A2…An, де n> 2, замінюючи його на наступний ряд нових правил A→ A1N(A2…An), N(A2…An)→ A2N(A3…An), …, N(An-1…An)→ An-1An (при цьому додаються нові нетермінальні символи N(A2…An), N(A3…An), …, N(An-1…An)).

Якщо для деяких A∈ N, B ∈ N і α ∈ (N UT)* множина P містить правила A → B, B → α, але не містить правила A → α, то додамо це правило в P. Повторюємо цю процедуру, доки можливо. Після цього видалимо із множини P всі правила вигляду A → B. Нарешті, змінимо S на S′, та додамо правила S′ → ε, S → S′ в тому випадку, коли мова L(G) містить порожній ланцюжок.

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

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

x =ϕ (x). Рекурсивне визначення можна тлумачити • операційно, тобто вказати алгоритм, за яким можна обчислити рекурсивно визначений об’єкт, • або денотаційно, тобто як рівняння, розв’язком якого є нерухомі точки (НТ) оператора ϕ. Зауваження 5.1 Тут на ϕ (x) ми дивимось синкретично (не розрізнюючи різні аспекти), та тлумачимо ϕ (x) або як вираз в певній алгебрі (коли говоримо про рівняння), або як оператор в цій алгебрі

(коли говоримо про нерухомі точки оператора). Зауваження 5.2 Часто також розглядаються системи рівнянь виду:

Такі системи зводяться до одного рівняння над послідовністю (x1, x2,..., xn).

Історія математики та логіки говорить про необхідність обережного поводження з рекурсією. Розглянемо приклад. Припустимо, що ми хочемо визначити суму 2 + 22 + 23 + 24 +.... Позначимо цю суму через x, тобто x = 2 + 22 + 23 + 24 +.... Якщо винести 2 з усіх членів суми, крім першого члена, отримаємо наступне рекурсивне визначення: x = 2 + 2x. Звідси x = – 2, що зовсім не відповідає очікуванню. Рекурсія може бути прихованою (неявною). Для ілюстрації розглянемо парадокс Рассела з теорії множин. А саме, множина x називається нормальною, якщо x ∉ x. Позначимо через N множину

сіх нормальних множин, тобто N ={ x | x ∉ x }. Парадокс виявляється, __ якщо запитати, чи є N нормальною множиною? Отримуємо, що N ∈ N тоді і тільки тоді, коли N ∉ N. Тут рекурсія виступає неявно, бо в визначенні N (неявно) припускається, що N може бути елементом N. Наведені приклади говорять про необхідність детального вивчення рекурсії, щоб уникнути некоректностей та парадоксів. Рекурсія широко використовується в мовах програмування. В таких випадках вона, як правило, визначається операційно, тобто вказується алгоритм, за яким можна обчислити рекурсивну процедуру або функцію. Традиційні проблеми, що розглядаються для такого роду рівнянь, є проблеми існування та опису всіх можливих розв’язків, зокрема, формулювання умов єдиності розв’язку. Існують різні методи розв’язку рекурсивних рівнянь. Найчастіше використовують метод послідовних наближень, який полягає у наступному. Береться початкове наближення d0. Далі обчислюється послідовність наближень (), (),.... d 1 =ϕ d 0 d 2 =ϕ d 1 За результат береться границя обчисленої послідовності: a= Зауваження 5.3 В теорії найменших нерухомих точок зазвичай використовується позначення виду i ∈ ω, де ω – перший нескінченний ординал, тобто ω ={ 0, 1, 2,...} – множина натуральних чисел.

Метод послідовних наближень графічно представлений на малюнку 5. 1. Наближення d 0, d 1, d 2... мають границю d, яка є коренем рівняння x =ϕ (x).

31. Властивості контекстно-вільних мов. Операції над формальними мовами. Дерева виводу

32. Застосування теорії ННТ. Уточнення синтаксису мов програмування