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

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

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

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

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