Синтез скінченних автоматів
(Перенаправлено з Синтез скінченного автомата)
Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову.
Конструкція Томпсона - це спосіб побудови НДСкА який розпізнає мову заданого регулярного виразу. Придуманий Кеном Томпсоном для реалізації регулярних виразів в текстовому редакторі 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) (англ.)
![]() |
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
![]() |
Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її. |