1. Вступ У цьому рефераті будуть дані визначення детерміні-рова і недетермінірованних
кінцевих автоматів, приведе-ни їх графи. Далі буде розглянутий
випадок перетворення недетермінірованного кінцевого автомата в детермінований
з малюнками та графами. Всі розглянуті тут автомати представлені як
маши-ни, що розпізнають ланцюжка символів. 2. Детерміновані кінцеві автомати.
У різних джерелах наводяться кілька відрізняють-ся один від одного визначення
детермінованого кінцевого автомата. Наведемо тут визначення з
джерела [2]. Детермінованим кінцевим автоматом (ДКА) називається машина, що розпізнає
ланцюжка символів. Вона має вхідну стрічку, розбиту на клітини, головку
на вхідних стрічці (вхід-ву головку) і керуючий пристрій з кінцевим числом
станів (рис. 1). Кінцевий автомат М можна представити у вигляді п'ятірки (S,
I, 1б 0, 1s0 0, F), де 1) S - безліч станів 1управляющего пристрої 0,
2) I - 1входной алфавіт 0 (кожна клітина вхідний стрічки з-тримає символ з
I), 3) 1б 0 - відображення з S x I в S (якщо 1б 0 (1s 0, 1a 0) = 1s '0, то
кожного разу, коли М перебуває в стані 1s 0, а вхідні головка оглядає
символ 1a 0, М зрушує вхідні головку праворуч і переходить в стан 1 s '0),
4) 1 s0 0 - виділене стан в S, зване 1начальним 0, 5) F - підмножина
в S, зване безліччю 1допуска-1ющіх 0 (або 1 заключних 0) 1
станів 0. 1b 0 1a 0 1c 0 Вхідна стрічка
^ Головка 1s 0 Керуючий пристрій
Рис. 1. Кінцевий автомат ДКА виконує кроки, які визначаються поточним станом його
блоку керування та вхідних символом, які оглядаються вхідний головкою. Кожен крок
складається з переходу в новий стан та зсуву вхідної головки на одну клітку
вправо. Надає-ся, що мова представимо регулярним [2] виразом тоді і тільки
тоді, коли він допускається деяким кінцевим авто-матом. Далі буде приведено
визначення ДКА через визначення недетермінірованного кінцевого автомата
(НКА), тобто можна буде розглядати ДКА як підмножини НДКА.
2. Недетермінірованние кінцеві автомати Для кожного стану і кожного вхідного
символу НКА має нуль або більше варіантів вибору наступного кроку. Він може також
вибирати, зрушувати йому вхідні головку при з-трансформаційних змін стану чи ні.
Наведемо визначення недетермінірованного кінцевого ав-томата. Недетермінірованним
кінцевим автоматом називається п'ятого-терка (S, I, 1 б 0, 1 s0 0, F), де 1) S
- Кінцеве безліч станів пристрої управ-ня; 2) I - 1 алфавіт 0 вхідних
символів; 3) 1б 0 - 1функція переходів 0, що відображає S x (IU (1e 0))
в безліч підмножин множини S; 4) 1 s0 0 (- S - 1 початковий стан 0
пристрої управління; 5) F _ (. S - безліч 1заключітельних (допускають)
0сос-тояній. З кожним НКА пов'язаний орієнтований граф, природним чином представляє
функцію переходів цього автомата. Наведемо визначення для графа
(Або діаграми) перех-дів автомата М = (S, I, 1б 0, 1s0 0, F). Графом переходів
автомата М називають орієнтований граф G = (S, E) з поміченими ребрами.
Безліч ребер Е і мітки визначаються в такий спосіб. Якщо 1б (s, a) 0содержіт
1s '0для деякого 1a 0 (- IU (1e 0), то ребро 1 (s, s') 0прінадле-
жит Е. міткою ребра 1 (s, s ') 0служіт безліч тих 1b 0 (- IU (1e 0), для
яких 1 б (s, b) 0 містить 1 s '0. Наприклад на рис. 2. зображено граф переходів
для неко-торого НКА. Заключне стан обведено подвійний рам-кою.
 1a, b 0 v 1a 0 1s1 0
1s2 0 ^ 1e 0
 1b 1e 0 v ===== 1s4 0?
1s3 0 ===== 1 a 0 Рис. 2. Приклад графа переходів
Для подальшого розгляду питання приведення недер-міновані кінцевого автомата
до детермінованому, піт-ребуется вказати кілька теорем. Теореми
наведені без доведення, для їх детального розгляду пропонується звернутися
до [2]. _Теорема 1. . Всякий мову, що допускається недермінірованним кінцевим
автоматом регуляро. _Теорема 2. . Нехай 2а 0 - регулярний вираз. Тоді най-
дется НКА М = (S, I, 1б 0, 1s0 0, (1Sf 0)), що допускає мова, предс-тавленний
2а 0, і що володіє такими властивостями: 1) S (/)}. Далі за допомогою індукції
по 1w 0, можна довести, що (1 (s0), w) 0 м *''(S, 1e 0) тоді і
тільки тоді, коли S = 1 (t (s0, w) 0 м * '1 (t, e)) 0. Отже L (M) =
L (M ') = L (M''). Що й треба було довести. 4. Приклад перетворення НКА в ДКА
На основі наведеного вище докази, розглянемо приклад для довільного
НКА М (рис. 3). Наведемо його з недетермінірованного виду в детермінований
аналог. 1b 1a 0
1s2 0? 1a 0 v 1 0 ^ 1e 0
===== 1s1 0 1s4 0 ===== ^
    1e 0 1e 0 1s3 0
 Рис. 3. Приклад недетермінірованного автомата НКА М З початкового
стану s1 можна досягти s3 і уклади-вування стан s4 по коліях,
поміченим символом 1е 0. Пое-тому для обчислення рефлексивного і транзитивного
замикання G 'орієнтованого графа G, про який йшла мова в доказів-будівництві
теореми 3, треба додати ребро (s1, s4). Весь граф G 'зображений на рис. 4. За
М і G 'побудуємо НКА М' (рис. 5). Так як у вузол s4 входять ребра з усіх уз-лов
графа G ', то оголошує всі стани в М' заключітель-ними.
 v 1s1 0 1s2 0?
                 v v v
 1s3 0 1s4 0
^ Рис. 4. Граф G 'Так єдине ребро, що входить у вузол s3 в
діаграмі для М, позначений символом 1 е 0, то s3 не входить в М '. 1b
 v ===== 1 a, b 0 ===== 1a 0 ===== 1s1 0
 1s2 0? 1s4 0 ===== ===== ===== ^
1a Рис. 5. НКА М 'При побудові ДКА М''по автомату М' утворюється вісім станів.
Але тільки чотирьох з них можна досягти з на-чільного стану, так що
інші чотири можна вики-сить. Наведений до детермінованому увазі автомат
М''при-наведено на рис. 6. Таким чином було показано можливість приведення
НКА до ДКА. При такій операції оцінок станів мо-жет істотно
збільшитися, деякі з них стають непотрібними. Сутність приведення полягає
в тому, що ми шукаємо обхідні шляхи для досягнення кінцевого стану,
прагнучи до того, щоб зникла неоднозначність переходу зі стану в стану
в залежності від вхідного символу. Ця операція породжує несуттєві стану
і тому, мабуть, в кожному з окремих випадків вирішувати завдання потрібно виходячи
їх конкретних цілей. 1b 0 ======= 1 b 1 (s2, s4) 0
 ======= V 1a 0 1 (/) 0? =====
 1 (s1) 0 ^ ===== v 1a 0 ===== 1b 0 1 a, b 1 (s2) 0
 ===== ^ 1b Рис. 6. ДКА G''
Для прикладу оцінки вартості перетворення НКА в ДКА розглянемо задачу розпізнавання
образів, в якій дана це-нирка-текст x = a1 a2 ... an і регулярний вираз
2а 0, на-зване чином. Ми хочемо знайти такий найменший індекс j,
що для деякого i подцепочка ai ai +1 ... aj ланцюжка x належить мові, представленому
виразом 2 а 0. Питання такого роду часто виникають при редагуванні
текстів. Багато програм для редагування текстів вирішуються користувачеві
задавати типи замін у ланцюжку-тексті. Наприклад користувач може сказати,
що він хоче замінити слово y якимось іншим словом у шматку тексту х. Щоб
ви-конати таку операцію, програма редагування тексту повинна зуміти знайти
входження слова у в текст х. Деякі потужні редагуйте програми дозволяють
користувачеві в ка-честве безлічі замінних ланцюжків вказувати регулярне
безліч. Наприклад користувач може сказати: "Замінити [I *] в х порожній ланцюжком",
маючи на увазі, що в х слід стерти пару квадратних дужок і символи між
ними. Поставлену вище завдання можна переформулювати, заме-нив дане регулярне
вираз 2а 0вираженіе 2b 0 = I * 2a 0, де I - алфавіт ланцюжка-тексту.
Можна знайти перше входження це-нирки з L (2a 0) в х = а1 а2 ... аn, виявивши
найкоротший пре-фікс ланцюжка х, що належить мові вирази 2b 0. Це завдання
можна вирішити, побудувавши НКА М для розпізнавання множини, представленого
виразом 2b 0, а потім визначити безліч станів у які може перейти
НКА М при прочитанні це-нирки а1 а2 ... аn. Один зі способів моделювання поведінки
НКА М на це-нирці-тексті х - перетворити М в детермінований кінцевий
автомат, використовуючи теорему 3. Однак такий шлях виявиться досить дорогим,
оскільки від регулярного висловлю-вання 2b 0можно перейти до НКА з 2 2b 0
станами, а потім до ДКА з майже 2 в ступені 2 2b 0 станами. Таким чином
вже сама побудова ДКА може викликати непереборні труднощі.