Синтез скінченних автоматів
Перейти до навігації
Перейти до пошуку
Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову.
Конструкція Томпсона - це спосіб побудови НДСкА який розпізнає мову заданого регулярного виразу. Придуманий Кеном Томпсоном для реалізації регулярних виразів в текстовому редакторі QED для Compatible Time-Sharing System.
Регулярний вираз | Відповідна йому регулярна мова | Відповідний йому НДСкА |
---|---|---|
- різні регулярні вирази | - різні мови | } - автомати що не містять спільних станів |
Заключний стан в об'єднанні єдиний! Заключні стани обох автоматів перестають бути заключними. | ||
Хоча краще злити вхід і заключний стан | ||
Варто також зауважити, що автомат зручніше будувати, коли регулярний вираз записаний у формі ПОЛІЗ.
Перед тим як застосовувати автомат для перевірки рядків на відповідність шаблону, його детермінізують та мінімізують.
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- Роджерс Х. . Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
- Russ Cox Regular Expression Matching Can Be Simple And Fast (англ.)
- Відео з поясненням конструкції Томпсона (YouTube) (англ.)
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її. |