Синтез скінченних автоматів

Конструкція Томпсона - це спосіб побудови НДСкА який розпізнає мову заданого регулярного виразу. Придуманий Кеном Томпсоном для реалізації регулярних виразів в текстовому редакторі QED для Compatible Time-Sharing System.

Регулярний вираз	Відповідна йому регулярна мова	Відповідний йому НДСкА
${\displaystyle \emptyset }$	${\displaystyle \emptyset }$
${\displaystyle x,\ x\in \Sigma \cup \{\epsilon \}}$	${\displaystyle \{x\}}$
${\displaystyle {\begin{array}{r}r_{1}\\r_{2}\end{array}}}$ - різні регулярні вирази	${\displaystyle {\begin{array}{r}L(r_{1})\\L(r_{2})\end{array}}}$ - різні мови	} - автомати що не містять спільних станів
${\displaystyle r_{1}+r_{2}}$	${\displaystyle L(r_{1})\cup L(r_{2})}$	Заключний стан в об'єднанні єдиний! Заключні стани обох автоматів перестають бути заключними.
${\displaystyle r_{1}r_{2}}$	${\displaystyle L(r_{1})L(r_{2})}$	Хоча краще злити вхід ${\displaystyle A_{2}}$ і заключний стан ${\displaystyle A_{1}}$
${\displaystyle r_{1}^{*}}$	${\displaystyle L(r_{1})^{*}}$

Варто також зауважити, що автомат зручніше будувати, коли регулярний вираз записаний у формі ПОЛІЗ.

Перед тим як застосовувати автомат для перевірки рядків на відповідність шаблону, його детермінізують та мінімізують.

1. Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (вид. 2). Addison-Wesley.
2. Russ Cox Regular Expression Matching Can Be Simple And Fast (англ.)
3. Відео з поясненням конструкції Томпсона (YouTube) (англ.)