Синтез скінченних автоматів
(Перенаправлено з Схема Томпсона)
Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову.
Конструкція Томпсона - це спосіб побудови НДСкА який розпізнає мову заданого регулярного виразу. Придуманий Кеном Томпсоном для реалізації регулярних виразів в текстовому редакторі QED для Compatible Time-Sharing System.
Регулярний вираз | Відповідна йому регулярна мова | Відповідний йому НДСкА |
---|---|---|
![]() | ||
![]() | ||
- різні регулярні вирази | - різні мови | ![]() |
![]() | ||
![]() | ||
![]() |
Варто також зауважити, що автомат зручніше будувати, коли регулярний вираз записаний у формі ПОЛІЗ.
Перед тим як застосовувати автомат для перевірки рядків на відповідність шаблону, його детермінізують та мінімізують.
![]() |
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
![]() |
Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її. |
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (вид. 2). Addison–Wesley.
- Russ Cox Regular Expression Matching Can Be Simple And Fast (англ.)
- Відео з поясненням конструкції Томпсона (YouTube) (англ.)