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

(Перенаправлено з Конструкція Томпсона)

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

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

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

Регулярний вираз Відповідна йому регулярна мова Відповідний йому НДСкА
     
     
  - різні регулярні вирази   - різні мови   } - автомати що не містять спільних станів
     
Заключний стан в об'єднанні єдиний! Заключні стани обох автоматів перестають бути заключними.
     
Хоча краще злити вхід   і заключний стан  
     

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

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



Посилання ред.

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