Елементарна подія в алфавіті X={x1,…,xn} є (n+1)-одноелементною подією x1, …, xn , е, де е - порожнє слово.
Регулярну подію можна отримати з елементарних подій застосуванням скінченного числа операцій ітерації, множення та диз’юнкції.
1.6.3 Регулярний вираз, циклічна глибина регулярного виразу та регулярної події
Регулярним виразом називають подання регулярної події через елементарні події та операції ітерації, множення та диз’юнкції.
Одна і та ж сама подія допускає багато різних представлень.
Циклічною глибиною регулярного виразу називають максимальне число вкладених пар ітераційних дужок, з яких складається даний вираз.
Наприклад: регулярний вираз x {y Ú {x} } має циклічну глибину 2 (складається з двох пар ітераційних дужок), а вираз x Ú yz - циклічну глибину 0.
Циклічною глибиною регулярної події називають найменшу циклічну глибину регулярних виразів, якi представляють дану подію.
Твердження: скінченні події та тільки вони є регулярними подіями, що мають нульову циклічну глибину.
Наслідок: лише використання ітерації дозволяє будувати регулярні вирази для нескінченних подій.
У той самий час, не всі нескінченні події є регулярними.
1.6.4 Приклад С.К. Кліні нескінченної нерегулярної події
Приклад нескiнченної нерегулярної події першим навів С.К.Кліні.
Таким прикладом є подія S, яка складається зі всіх слів у кінцевому алфавіті X, довжини яких є точними квадратами (тобто слова події S мають довжину 1, 4, 9, 16, 25 тощо).
1.6.5 Теорема Кліні про зв’язок скінченних автоматів і регулярних подій, наслідок теореми Кліні
Теорема Кліні (про зв’язок кінцевих автоматів і регулярних подій). Нехай задано деяку множину М подій S1,…,Sn у деякому кінцевому алфавіті Х. Кожна з подій множини М тоді та тільки тоді може бути представлена в кінцевому автоматі деякою множиною його станів або вихідних сигналів, коли кожна з подій множини М є регулярною подією.
Наслідок теореми Клiнi. Умова, яку необхідно накласти на нескінченну область визначення алфавітного оператору для того, щоб можна було побудувати кінцевий автомат, який реалізує даний алфавітний оператор, полягає в тому, що вказана область визначення повинна бути регулярною подією.
1.7 Структурна теорія автоматів
1.7.1 Основні положення структурної теорії автоматів, поняття про композицію автоматів i структурну схему, головні відмінності структурної й абстрактної теорії автоматiв
У порівнянні з абстрактною теорією автоматів, у структурній теорії автоматiв робляться подальші кроки в напрямку враховування більшої кiлькостi властивостей реально існуючих дискретних автоматів.
Головна відмінна риса структурної теорії автоматів полягає в тому, що, на відміну від абстрактної теорії автоматiв, враховується структура вхідних і вихідних сигналів автомату, а також його внутрішня структура на рівні так званих структурних схем.
Основною задачею структурної теорії автоматiв є вивчення композиції автоматів, тобто методів побудови складних автоматів iз автоматів, що є відносно простiшими.
Структурна теорія автоматiв не ставить задачу відображення всіх властивостей реально існуючих автоматів.
Наприклад, не враховуються перехідні процеси в автоматах, питання надійності роботи автоматів, фізичні властивості сигналів і багато іншого.
У даному розумінні, структурна теорія автоматів також залишається в значній мірі абстрактною, хоча вона і відрізняється значно меншим ступенем абстракції, нiж абстрактна теорія автоматів.
Таким чином, структурна й абстрактна теорії автоматів є двома різними ступенями загальної теорії автоматів.
При синтезі реальних автоматів, багато питань простіше й ефективніше вирішуються на рівні абстрактної теорії автоматiв (до числа таких питань належать визначення необхідного обсягу пам'яті автомату, переходів у пам'яті, а також питання, що відносяться до мінімізації числа станів автомату).
Одночасно є ряд питань (таких, наприклад, як питання композиції автоматів), постановка яких виходить за рамки абстрактної теорії автоматів.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.