Конструкція Томпсона

Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову.

Конструкція Томпсона

Конструкція Томпсона - це спосіб побудови НДСкА який розпізнає мову заданого регулярного виразу. Придуманий Кеном Томпсоном для реалізації регулярних виразів в текстовому редакторі 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})^{*}}$

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

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

Джерела

• Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• (інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• Russ Cox Regular Expression Matching Can Be Simple And Fast (англ.)
• Відео з поясненням конструкції Томпсона (YouTube) (англ.)