Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову.
Конструкція Томпсона Конструкція Томпсона - це спосіб побудови НДСкА який розпізнає мову заданого регулярного виразу. Придуманий Кеном Томпсоном для реалізації регулярних виразів в текстовому редакторі QED для Compatible Time-Sharing System.
Регулярний вираз Відповідна йому регулярна моваВідповідний йому НДСкА - різні регулярні вирази - різні мови } - автомати що не містять спільних станів Заключний стан в об'єднанні єдиний! Заключні стани обох автоматів перестають бути заключними. Хоча краще злити вхід і заключний стан
Варто також зауважити, що автомат зручніше будувати, коли регулярний вираз записаний у формі ПОЛІЗ.
Перед тим як застосовувати автомат для перевірки рядків на відповідність шаблону, його детермінізують та мінімізують.
Джерела
Russ Cox Regular Expression Matching Can Be Simple And Fast Відео з поясненням конструкції Томпсона (YouTube)