- •Лабораторна робота 8
- •1 Основнi теоретичнi вiдомостi
- •1.1 Інформаційні основи цифрових автоматів
- •1.1.1 Поняття інформації, неперервний I дискретний підходи до вивчення навколишнього світу з інформаційної точки зору
- •1.1.2 Поняття інформації, неперервний I дискретний підходи до вивчення навколишнього світу з інформаційної точки зору, універсальність алфавітного способу подання інформації та його значення
- •1.1.3 Поняття про перетворення інформації, перетворювачі інформації, алфавітні оператори та проблеми їх задавання
- •1.2 Абстрактна теорія автоматів
- •1.2.1 Поняття про абстрактний автомат
- •1.2.3 Відображення, що породжуються абстрактними автоматами
- •1.2.2 Абстрактнi автомати першого та другого роду
- •1.4 Частковi абстрактнi автомати
- •1.4.1 Поняття часткового абстрактного автомату
- •1.4.2 Заборонені та допустимі слова для даного часткового автомату
- •1.4.3 Відображення, що породжується частковим автоматом, еквiвалентнi частковi автомати
- •1.4.4 Часткове відображення, що продовжує iнше часткове вiдображення, еквівалентне продовження часткового автомату
- •1.4.5 Початкові відрізки вхідного слова часткового автомату, умова повноти часткового вiдображення
- •1.4.6 Автоматні відображення, умови автоматності вiдображень
- •1.4.7 Теорема Хоффмена-Мілі
- •1.4.8 Обмеження, накладенi умовами автоматності на клас відображень, породжених частковим автоматом, операції вирівнювання слів I поповнення
- •1.5 Способи задавання автоматних вiдображень, поняття подiї, канонiчна множина подiй, алгебра подiй
- •1.5.1 Способи задавання автоматних вiдображень
- •1.5.2 Подія в довільному алфавіті; подія, представлена в автоматному вiдображеннi лiтерою вихідного алфавіту; канонічна множина подій
- •1.5.3 Теорема про зв'язок автоматного вiдображення φ iз відповідною йому канонічною множиною подій
- •1.7.1 Основні положення структурної теорії автоматів, поняття про композицію автоматів I структурну схему, головні відмінності структурної й абстрактної теорії автоматiв
- •1.7.2 Закони функціонування автоматів Мілі і автоматів Мура у структурній теорії автоматів
- •1.7.3 Основна задача структурної теорії автоматів
- •3 Індивідуальні контрольнi завдання
- •Вимоги до оформлення, захисту та оцінювання лабораторних робіт
- •Зразок оформлення титульного аркуша звіту про виконання лабораторної роботи
1.4 Частковi абстрактнi автомати
1.4.1 Поняття часткового абстрактного автомату
Частковим абстрактним автоматом (ЧА) називають абстрактний автомат, у якого функцiя переходiв, або функцiя виходiв, або обидві вказанi функції визначені не для всіх пар значень своїх аргументів (а, х).
На відміну від часткових абстрактних автоматiв, тi АА, що розглядалися раніше, називають повністю визначеними.
Для часткових абстрактних автоматiв застостовуються ті ж способи задавання, що й для повністю визначених АА.
У тих місцях таблиць ТП i ТВ, в яких відповідні їм функції не визначені, як правило, ставлять риску.
Граф часткового автомату може мати вершини, з яких не виходять стрілки, позначені тими або іншими вихідними сигналами.
Частковi автомати також розділяють на абстрактнi автомати першого та другого роду, автомати Мілі та Мура.
1.4.2 Заборонені та допустимі слова для даного часткового автомату
Для визначення поняття еквівалентності часткового автомату, необхідно встановити, що слід розуміти під відображенням, що породжується даним ЧА.
З даною метою, будемо подавати на вхід часткового автомату, приведеного завчасно до початкового стану, різноманітні вхідні слова.
Подаючи чергову лiтеру х(к) = хік на вхід ЧА, можна зіштовхнутися з ситуацією, коли відповідний їй вихідний сигнал не визначено.
Домовимось називати відповідне слово забороненим для даного ЧА.
Усі слова, які не є забороненими, називаються допустимими для даного часткового автомату.
1.4.3 Відображення, що породжується частковим автоматом, еквiвалентнi частковi автомати
Відображення множини вхідних слів у множину вихідних слів, що породжується частковим автоматом А, є частковим відображенням, областю визначення якого служить множина всіх допустимих слів даного часткового автомату.
Образ φ(р) будь-якого допустимого слова р при даному відображенні визначається так само, як і для повністю визначених абстрактних автоматiв.
Два часткових автомати з однаковими вхідними та вихідними алфавітами називають еквівалентними, якщо породжувані ними часткові відображення мають одну й ту ж саму область визначення та співпадають на даній області.
1.4.4 Часткове відображення, що продовжує iнше часткове вiдображення, еквівалентне продовження часткового автомату
Часткове відображення (ЧВ) φ продовжує часткове вiдображення ψ, якщо область визначення часткового вiдображення φ включає в себе область визначення М часткового вiдображення ψ, і на області М обидва відображення співпадають.
Частковий автомат А називають еквівалентним продовженням частко-вого автомату В, якщо те часткове вiдображення, що породжує частковий авто-мат А , продовжує часткове вiдображення, що породжує частковий автомат В.
1.4.5 Початкові відрізки вхідного слова часткового автомату, умова повноти часткового вiдображення
Із визначення допустимих слів (для будь-якого часткового автомату А) випливає наступне: якщо вхідне слово р= хі1. . . . . хік є допустимим, то допустимими будуть усі слова виду хі1, хі1хі2, . . ., хі1…хік-1, якi називають початковими відрізками слова р (за визначенням, до початкових відрізків слова р відносять саме слово р і порожнє слово е, що не містить жодної лiтери).
Наведенi визначення дозволяють сформулювати твердження: область визначення М будь-якого часткового відображення, що породжується частковим автоматом, задовольняє умові повноти: разом iз будь-яким словом області М, дана область також містить усі початкові відрізки вказаного слова.