Тема 4.1. Формальні граматики і мови.

Лекція 4.1.1 Граматики породження: визначення і класифікація. Алфавіти і мови: основні поняття і формальні визначення (слово, мова, операції над словами і мовами, їх властивості). Визначення граматик породження: термінальний і не термінальний алфавіти, правила породження, породжувані слова і мова. Класифікація граматик за Хомським: автоматні, контекстно-вільні, контекстно-залежні граматики та граматики без обмежень. Приклади граматик типів 0-3.

Лекція 4.1.2. Інші моделі граматик. Трансформаційні граматики. Програмні гаматики. Індексні граматики. Приклади програмних та індексних граматик, аналіз їх­ніх властивостей.

Лекція 4.1.3. Властивості контекстно-вільних мов як базис теорії трансляції. Контекстно-вільні граматики і мови. Дерева виведення. Виведення і дерева виведення. Проблема порожнечі мови. Властивості контекстно-вільних мов. Нормальні форми Хомського та Грейбах контекстно-вільних граматик та алгоритми зведення до них. Проблеми дослідження контекстно-вільних граматик та відповідні алгоритми.

Лекція 4.1.4. Контекстно-залежні граматики і граматики без обмежень. Властивості граматик без обмежень і контекстно-залежних граматик. Загальне уявлення про завдання алгоритмічних мов програмування граматиками. Форма Бекуса-Наура і розширена фор­ма Бекуса-Наура. Уявлення про граматику мови програмування Паскаль.

Тема 4.2. Алгебраїчні моделі формальних мов.

Лекція 4.2.1. Регулярні множини і праволінійні граматики. Властивості регулярних множин: визначення, зв'язок з регулярними виразами, розростання, бульова алгебра регулярних множин. Регулярні множини і автоматні граматики: еквівалентність класів регулярних множин і мов, які породжені автоматними граматиками.

Лекція 4.2.2. Алгебраїчні властивості мов. Алгебраїчні властивості регулярних мов. Операції над регулярними мовами і їх властивості. Алгебра подій. Алгебраїчні властивості контекстно-вільних мов. Операції над контекстно-вільними мовами і їх властивості. Алгебра контекстно-вільних мов.

Лекція 4.2.3. Алгебраїчні властивості контекстно-залежних мов і мов без обмежень.

Роздiл 5. Теорія авто­матів

Автомати як засоби моделювання динаміки об’єктів. Основні поняття теорії автоматів. Стани та їх зміна у просторі. Функціонування як переходи автомата. Застосування автоматів.

Тема 5.1. Скінчені автомати, їх аналіз і синтез.

Лекція 5.1.1. Скінчені автомати: визначення і загальна арактеристика. Основні поняття скінчених автоматів: стан, перехід, вихід, конфігурація і ситуація, такт. Скінчений автомат як математичний об’єкт і пристрій. Тривіальні і нетривіальні, детерміновані і недетерміновані автомати. Деякі властивості автоматів. Способи задання скінчених автоматів. Перерахування скінчених автоматів.

Лекція 5.1.2. Задача аналізу скінченних автоматів. Проблеми дослідження скінчених автоматів: аналіз, синтез, розпізнавання. Скінчені автомати і регулярні мови. Скінчений розпізнавач. Задача аналізу скінченого автомата і властивості графів і матриць переходів автомата.

Лекція 5.1.3. Функціонування автомата і формальні засоби його аналізу. Переходи в автоматі і необхідність їх дослідження. Дослідження маршрутів на основі операцій над матрицями переходів. Найкоротші шляхи. Замкнені шляхи. Кістякові матриці і їх застосування для аналізу автоматів.

Лекція 5.1.4. Еквівалентність станів скінченних автоматів. Еквівалентні і розрізнені стани. Умови еквівалентності і розрізненості станів. k-еквівалентні і k-розрізнені стани. Умови k-еквівалентності і k-розрізненості станів. Властивості відношення k-еквівалентності і k-розрізненості станів. k-еквівалентне розбиття та його властивості.

Лекція 5.1.5. Еквівалентне розбиття і матричний метод його визначення. Еквівалентне розбиття та його властивості. Розбиття та k-еквівалентне розбиття. Матричний метод визначення еквівалентного розбиття. Побудова початкової матриці і опис ітерації перетворень матриці автомата. Еквівалентність автоматів: визначення і властивості.

Лекція 5.1.6. Мінімальна форма і її властивості. Мінімальна форма скінченого автомата: визначення і властивості. Мінімальний автомат і його побудова. Приклади виконання мінімізації скінченого автомата.

Лекція 5.1.7. Експерименти по розпізнаванню станів. Класифікація експериментів: безумовні і умовні, прості і кратні, діагностичні і установочні експерименти. Діагностична і установочна задачі. Діагностичні експерименти для двох станів. Діагностична послідовність. Алгоритм побудови мінімальної діагностичної послідовності.

Лекція 5.1.8. Експерименти по розпізнаванню автоматів. Загальна задача розпізнавання автомата. Умови розпізнаваності і нерозпізнаваності автомата. Розпізнавання автоматів відомого класу. Умови розпізнаваності і нерозпізнаваності автомата відомого класу. Алгоритм побудови мінімальної діагностичної послідовності розпізнавання автоматів відомого класу.

Лекція 5.1.9. Задача синтезу скінченого автомата. Алгоритм синтезу скінченого автомата за регулярним виразом. Приклади скінчених автоматів для моделювання реальних об'єктів.