Студопедия

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

Разделы сайта

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






Комп'ютерні проекти






1. Булеву функцію п змінних задано таблицею. Побудувати досконалу ДНФ цієї функції.

2. Булеву функцію задано таблицею. Побудувати досконалу КНФ цієї функції.

3. Булеву функцію п змінних задано таблицею. Побудувати фор­мулу, що зображає цю функцію лише за допомогою операцій запе­речення та кон'юнкції.

4. Булеву функцію п змінних задано таблицею. Побудувати формулу, що зображає цю функцію лише за допомогою операцій заперечення та диз'юнкції.

5. Булеву функцію п змінних задано таблицею. Побудувати формулу, що зображає цю функцію лише за допомогою операції штрих Шеффера.

6. Булеву функцію п змінних задано таблицею. Побудувати формулу, що зображає цю функцію лише за допомогою операції стрілка Пірса.

7. Булеву функцію трьох змінних задано таблицею. Побудувати її карту Карно.

8. Булеву функцію чотирьох змінних задано таблицею. Побу­дувати її карту Карно.

9. (*) Булеву функціюп змінних задано таблицею. Побудувати скорочену ДНФ цієї функції методом Мак-Класкі.

Література

1. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискрет­ной математике. -М: Наука, 1977.

2. Глушков В. М. Синтез цифровых автоматов. - М.: Физматгиз, 1962.

3. Капітонова Ю. В., Кривий С. Л., Летичевський О. А., Луцький Г. М., Печурін М. К. Основи дискретної математики. - К.: Наукова думка, 2002.

2. Карпов В. Г., Мощенский В. А. Математическая логика и дискретная математика. - Минск: Вышэйшая школа, 1977.

3. Кузнецов О. ЩАдельсон-Вельский Г. М. Дискретная математика для инженера. -М.: Энергоатомиздат, 1988.

4. Пасічник В.В. Використання частково-визначених булевих функцій для аналізу реляційних моделей баз даних. // Респуб­ліканськийзбірник " Контрольно-вимірювальна техніка". - Львів, 1981.-С. 97-104.

5. ЦейтлінГ. Є. Елементи теорії булевих функцій. - К.: Техніка, 1973.

6. Щербина Ю. М. Елементи теорії булевих і обмежено-детермінованих функцій. - Львів: ЛДУ, 1981.

7. Яблонский С. В. Введение в дискретную математику. - ML: Наука, 1986.

8. RosenК. Н. DiscreteMathematicsandItsApplications. McGraw- Hill, 2002.


Розділ 9

Мови, граматики та автомати

План викладення матеріалу

Мови.

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

Типи граматик (ієрархія Хомські).

Дерева виведення.

Форми Бекуса-Наура.

Скінченні автомати з виходом.

Скінченні автомати без виходу.

Подання мов.

Задачі.

Комп 'ютерні проекти.

Література.

Мови

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

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

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

де V 0={λ }.

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

a 0=λ; aa = a 2; aan -1= an

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

Множину ланцюжків (або речень) називають мовою. Формально моваL над алфавітом V- це множина ланцюжків уV*, томуL⊂ V*.

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

Рис. 9.1

Зараз звернемо увагу на те, як слова можна складати у речення, а множина всіх речень, які мають смисл, утворюють мову. Нас будуть здебільшого цікавити формальні мови, такі як мови програ­мування або мови, які описують правильні математичні вирази. Проте спочатку буде корисно навести приклад природної мови.

Приклад 9.1. Розглянемо речення

Маленька дівчина нагодувала котика.

Головним об'єктом розгляду будуть питання синтаксису. Щоб проілюструвати клас структур, які вивчатимемо, розглянемо діаг­раму на рис. 9.1. Ця діаграма означає, що можна побуду­вати за допомогою злиття і , хоча це потребує формального означення. Група підмета складається з і , а група присудка-з і . Остаточно отримаємо " маленька", " дівчина",..., що дає нам речення " маленька дівчина нагодувала котика". ▲

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

Нагадаємо, що для заданого алфавітуV моваL є довільною підмножиною множиниV*, проте довільні підмножини становлять незначний інтерес. Зосередимо увагу на спеціальних мовах, у яких ланцюжки, завдяки зовнішній інформації про їхню семантику, вважають осмисленими або добре сконструйованими.

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

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

2. Як за заданимиL⊂ V*та α ∈ V* з'ясувати, чи α ∈ L?

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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.