Синтез скінченних автоматів
Перейти до навігації
Перейти до пошуку
Задача синтезу скінченного автомата полягає в створенні такого автомата акцептора, який би розпізнавав дану регулярну мову.
Конструкція Томпсона[ред. | ред. код]
Конструкція Томпсона - це спосіб побудови НДСкА який розпізнає мову заданого регулярного виразу. Придуманий Кеном Томпсоном для реалізації регулярних виразів в текстовому редакторі QED для Compatible Time-Sharing System.
Регулярний вираз | Відповідна йому регулярна мова | Відповідний йому НДСкА |
---|---|---|
- різні регулярні вирази | - різні мови | } - автомати що не містять спільних станів |
Заключний стан в об'єднанні єдиний! Заключні стани обох автоматів перестають бути заключними. | ||
Хоча краще злити вхід і заключний стан | ||
Варто також зауважити, що автомат зручніше будувати, коли регулярний вираз записаний у формі ПОЛІЗ.
Перед тим як застосовувати автомат для перевірки рядків на відповідність шаблону, його детермінізують та мінімізують.
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її. |
Посилання[ред. | ред. код]
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (вид. 2). Addison–Wesley.
- Russ Cox Regular Expression Matching Can Be Simple And Fast (англ.)
- Відео з поясненням конструкції Томпсона (YouTube) (англ.)