- •Лабораторна робота 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.6 Автоматні відображення, умови автоматності вiдображень
Відображення (взагалі кажучи, часткові), що породжуються абстрактним автоматом, називають автоматними відображеннями (АВ).
Зi способу визначення автоматного вiдображення, безпосередньо випливає, що будь-яке автоматне вiдображення вiдповiдає наступним чотирьом умовам, які називаються умовами автоматності відображення:
1) автоматне вiдображення здійснює однозначне відображення (взагалі кажучи, часткове) множини слів в деякому скінченному алфавіті х (вхідному алфавітi автоматного вiдображення) у множину слів в деякому скінченному алфавіті у (вихідному алфавітi автоматного вiдображення);
2) область визначення автоматного вiдображення вiдповiдає умові повноти; за визначенням, порожнє слово завжди входить до областi визначення автоматного вiдображення;
3) автоматне вiдображення φ зберігає довжину слова: будь-яке слово р у вхідному алфавіті х (на якому у визначено) має ту ж довжину, що й його образ φ(р); порожнє слово теж переводиться при відображенні φ у порожнє слово;
4) автоматне вiдображення переводить будь-який початковий відрізок слова р (на якому автоматне вiдображення визначене), у відповідний (такий, що має ту саму довжину) початковий відрізок слова φ(р).
1.4.7 Теорема Хоффмена-Мілі
Теорема Хоффмена-Мілі: якщо автоматне відображення φ вiдповiдає чотирьом умовам автоматності, то можна побудувати абстрактнi автомати Мілі та Мура (взагалі кажучи, нескінченні), що продовжують дане автоматне вiдображення; якщо область визначення відображення φ є скінченною, то абстрактнi автомати Мілі та Мура також можуть бути побудовані скінченними.
Основною метою є формування більш загального результату, що дозволив би побудувати такi скінченні автомати Мілі та Мура, що породжують задане автоматне вiдображення не тільки для скінченної області визначення автоматного вiдображення, а й кожного разу, коли такі автомати існують.
1.4.8 Обмеження, накладенi умовами автоматності на клас відображень, породжених частковим автоматом, операції вирівнювання слів I поповнення
Умови автоматності накладають досить жорсткі обмеження на клас відображень, які можуть бути породжені абстрактним автоматом: більшість автоматних вiдображень (зокрема, алгоритмів), з якими мають справу на практиці, не вiдповiдають указаним умовам.
Але існує стандартний прийом, який дозволяє перетворити будь-яке однозначне алфавітне відображення на автоматне, базуючися на застосуванні двох операцій (вирівнювання слів та поповнення), завдяки чому, обмеження, накладенi умовами автоматності, виявляються неістотними.
1.5 Способи задавання автоматних вiдображень, поняття подiї, канонiчна множина подiй, алгебра подiй
1.5.1 Способи задавання автоматних вiдображень
Можна задавати автоматне вiдображення автоматом, який його породжує.
Але на практиці, при постановці задач синтезу автоматiв, даний спосіб задавання є кінцевою метою, а не початковим етапом.
У випадку, коли область визначення автоматного вiдображення φ є скінченною, його, як правило, задають за допомогою таблиці відповідності.
Використовуючи четверту умову автоматності, до таблицi виходiв не включають вхідні слова, що є початковими відрізками слів, які уже були включені до таблицi.
У результаті, отримують так звану скорочену таблицю виходiв.
Інколи за допомогою таблиць можна завдавати автоматнi вiдображення з нескінченною областю визначення.
Найбільш поширеним способом задавання довільного автоматного вiдображення є його задавання за допомогою автоматної множини подій.