“Основи Дискретної математики“

Теоретичні питання З предмету: “Основи Дискретної математики“

9. Мови. Формальні породжу вальні граматики.

Буква (або символ) - це простий неподільний знак; множина букв утворює алфавіт V. Алфавіти є множинами, і тому до них можна застосовувати теоретико -множинні позначення.

Ланцюжки (string) над алфавітом V- це впорядковані сукупності букв алфавіту V, отже, вони виглядають як елементи Vn=VxVx.. .xV. Проте, буде природнішим записувати їх у вигляді а1,a2...ап, а не (а1,а2 ап). Букви є ланцюжками у разі п=1. Будемо допускати випадок, коли ланцюжок не містить букв (порожній ланцюжок), і позначатимемо такий ланцюжок через . Зазначимо, що , не є символом, тобто не належить V для будь-якого алфавіту V.

За аналогією з лінгвістикою ланцюжки іноді називають словами. Множину всіх ланцюжків над алфавітом V називають замиканням V і позначають V*.

Головну операцію над ланцюжками називають конкатенацією. Нехай а та b - ланцюжки над алфавітом V. Конкатенацією а та b називають ланцюжок c=ab (тобто до ланцюжка а дописано ланцюжок Ь). Якщо ланцюжок складається з символів, що повторюються, то використовують скорочені позначення: для а є V і цілого невід'ємного п записують:

a0=л; aa=a2;aan-1=an

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

Множину ланцюжків (або речень) називають мовою. Формально мова L над алфавітом V— це множина ланцюжків у V. Правила, які визначають множину речень, утворюють синтаксис мови, опис множини смислів і відповідності між реченнями і смислами - семантику мови. Семантика мови залежить від характеру об'єктів, які описує мова, і засоби її вивчення для різних типів мов різні. Семантика мови математики - формальні теорії. Дослідження семантики мов програмування стало самостійною частиною теоретичного
програмування. Спроби точного опису семантики природних мов стосуються, передусім, робіт з машинного перекладу. Щодо синтаксису, то його особливості значно менше залежать від призначення мови. Виявилось можливим сформулювати поняття і методи дослідження синтаксису, які не залежать від змісту і призначення мов. Тому найбільших успіхів математична лінгвістика досягла у вивченні синтаксису, де за останні 50 років розвинувся
спеціальний математичний апарат-теорія формальних породжувальних граматик. Ця теорія дуже важлива теоретично й ефективна у застосуваннях (мови програмування, штучний інтелект, машинний переклад). У цьому розділі вивчаються головні поняття теорії формальних граматик і показаний зв'язок між граматиками й автоматами.

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

Як за заданою граматикою G (і пов'язаною з нею мовою L) породжувати речення а: а є L?

Як за заданими LcV* та aєV з'ясувати, чи а є L?

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

2. Формальні породжувальні граматики

У лінгвістиці природних мов терміни "речення" й "слово" мають різний смисл; тому в математичній лінгвістиці послідовність символів звичайно називають нейтральним терміном "ланцюжок" (string), a мову, яку розуміють як множину формальних ланцюжків, -формальною мовою.

Формальна породжувальна граматика G (у подальшому граматика G) - це формальна система, визначена четвіркою об'єктів G={ V, T,S,P), де V- скінченна непорожня множина, яку називають алфавітом (або словником); Т—її підмножина, елементи множини Т називають термінальними (основними) символами; S-початковий символ (S належить V), Р - скінченна множина продукцій (або правил перетворення).

Множину V\T позначають N, її елементи називають нетермінальними (допоміжними) символами.

Формальні породжувальні граматики часто називають граматиками з фразовою структурою (phrase-structure grammar), граматиками безпосередніх складових. Термінальні символи часто називають терміналами, а нетермінальні символи - нетерміналами.

У теорії формальних граматик усталилися традиції позначень, яких будемо дотримуватись. Символи термінального алфавіту прийнято позначати малими латинськими буквами або цифрами, символи нетермінального алфавіту - великими латинськими буквами, ланцюжки в алфавіті V — грецькими буквами. Довжину ланцюжка а позначають L(a) або |а|. Нагадаємо, що множину всіх ланцюжків в алфавіті V позначають V*.

Практичні завдання З предмету: “Основи Дискретної математики“

9.

a | b | c

0 | 0 | 0 | 0 | 0 | 0 | 1 | 0

0 | 0 | 1 | 1 | 1 | 0 | 0 | 1

0 | 1 | 0 | 1 | 0 | 0 | 0 | 1

0 | 1 | 1 | 1 | 1 | 0 | 0 | 1

1 | 0 | 0 | 0 | 1 | 0 | 0 | 1

1 | 0 | 1 | 1 | 0 | 1 | 0 | 0

1 | 1 | 0 | 1 | 1 | 0 | 0 | 1

1 | 1 | 1 | 1 | 0 | 1 | 0 | 0

“Об’єктно-орієнтоване програмування”

Теоретичні питання З предмету: “Об’єктно-орієнтоване програмування “

9. Обробка виключних ситуацій в програмному застосуванні

Для розміщення об'єкту в динамічній пам'яті використовують процедуру або функцію New:

процедура

New (< ім'я покажчика >);

функція

< ім'я покажчика >:=New(< тип « покажчик на клас »>).

Якщо динамічний об'єкт використовує віртуальні методи класу, то до звернення до цих методів він повинен викликати конструктор (роздягнув 2.3):

<