Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




Визначення 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. Далі обчислюється послідовність наближень ( ), ( ) ,... . d1 =ϕ d0 d2 =ϕ d1 За результат береться границя обчисленої послідовності: a= Зауваження 5.3В теорії найменших нерухомих точок зазвичай використовується позначення виду i∈ω, де ω – перший нескінченний ординал, тобто ω={0, 1, 2, . . .} – множина натуральних чисел.

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



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


 

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


.

mylektsii.ru - Мои Лекции - 2015-2020 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал