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

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

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

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

Регулярний вираз	Відповідна йому регулярна мова	Відповідний йому НДСкА
$\emptyset$	$\emptyset$	Файл:Tompson emptyset.png
$x, x \in Σ \cup {ϵ}$	${x}$	Файл:Tompson one char.png
$\begin{matrix} r_{1} \\ r_{2} \end{matrix}$ - різні регулярні вирази	$\begin{matrix} L (r_{1}) \\ L (r_{2}) \end{matrix}$ - різні мови	Файл:Tompson two FA.png } - автомати що не містять спільних станів
$r_{1} + r_{2}$	$L (r_{1}) \cup L (r_{2})$	Файл:Tompson add.pngШаблон:Clear Заключний стан в об'єднанні єдиний! Заключні стани обох автоматів перестають бути заключними.
$r_{1} r_{2}$	$L (r_{1}) L (r_{2})$	Файл:Tompson mult.pngШаблон:Clear Хоча краще злити вхід $A_{2}$ і заключний стан $A_{1}$
$r_{1}^{*}$	$L (r_{1})^{*}$	Файл:Tompson closure.png

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

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