Кінцеві автомати

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?? <= 2? 2a 0?, Де? 2а 0? - Довжина вираження 2 а 0,>
2) для кожного 1a 0 (- IU (1e 0) безліч 1 б (Sf, a) 0 порожньо,
3) для кожного 1s 0 (- S сума чисел?? 1б (s, a) 0?? По всіх 1а
з IU (1e 0) не перевершує 2.
Ці теореми будуть використані при перетворенні НКА в
ДКА у наступному пункті.
3. Перетворення НКА в ДКА
Існує додатковий результат або можливість з-
поставити будь-якому взятому НКА еквівалентну "детерміні-
рованную "машину. Однак детермінований кінцевий авто-
мат, еквівалентний даному НКА з n станами, може мати
аж до 2 в n ступеня станів. Тому перехід від НКА до
детермінованому автомата не завжди дає ефективний спо-
соб моделювання недетермінірованного кінцевого автомата.

Однак ДКА дозволяють простіше формалізувати модель автомата та
алгорітмізіровать його поведінку. Крім цього детермінує-
ванні автомати застосовуються при розпізнаванні образів.
Таким чином ми можемо дати визначення ДКА як подмно-
дружність або окремого випадку НКА.
Детермінованим кінцевим автоматом називається неде-
термінірованний кінцевий автомат (S, I, 1б 0, 1s0 0, F), в кото-
ром:
1) 1 б (s, e) 0 = (/) (порожня множина) для всіх 1 s 0 (- S,
2)?? 1б (s, a) 0?? <= 1 для всіх 1 s 0 (- S і 1 а 0 (- I.>
Наведемо теорему, яка допоможе зв'язати і висловити
недетермінірованний кінцевий автомат через його детермінують-
ний еквівалент.
_Теорема 3. . Якщо L - регулярне безліч, то воно допус-
кається деяким ДКА.
Доказ. За теоремою 1 L допускається деяким
НКА М = (S, I, 1б 0, 1s0 0, (1Sf 0)). Перетворимо М в ДКА наступним
чином. Спочатку знайдемо такі пари станів 1 (s, t) 0, що
1 (s, e) 0?? м * 1 (t, e) 0. Щоб зробити це, побудуємо орієнтир-
ний граф G = (S, E), у якого 1 (s, t) 0прінадлежіт Е
тоді і тільки тоді, коли 1б (s, e) 0содержіт 1t 0. Потім ви-
числах рефлексивне і Транзитивне замикання G '= (S, E')
графа G. Ми стверджуємо, що 1 (s, e) 0?? м * 1 (t, e) 0тогда і
тільки тоді, коли 1 (s, t) 0 належить Е '.
Тепер побудуємо такий НКА М '= (S', I, 1б 0 ', 1s0 0, F), що
L (M ') = L (M) і в М' немає 1 е 0 - переходів.
1) 1S '= (s0) U (t? Б (s, a) 0содержіт 1t 0для деякого 1s
(- S і деякого 1а 0 (- I 1) 0.
2) Для кожного 1 s 0 (- S 'і кожного 1 а 0 (- I
1б '(s, a) = (u? (S, t) 0 (- E' і 1 б (t, a) 0 містить 1 u) 0.
3) F '= 1 (s? (S, f) 0 (- E' і 1 f 0 (- F 1) 0.
Таким чином L (M) = L (M ') і в M' немає переходів по 1 е 0.
Далі по M 'побудуємо ДКА M'', стану якого обра-
зуются безліч-ступінь для S '. Іншими словами, M''=
(1P 0 (S '), I, 1 б''0, (1s0 0), F''), де
1) для кожного підмножини S безлічі S 'і кожного 1а
(- I
1б''(S, a) = (t? Б '(s, a) 0содержіт 1t 0для деякого 1s 0 (-

S 1) 0,
2) F''= (S? S П F (/)}. Далі за допомогою індукції по? 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? станами.
Таким чином вже сама побудова ДКА може викликати
непереборні труднощі.