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

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

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

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

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

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

Посилання

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) (англ.)