Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов:
1. * Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
2. * Вычисление множеств <tex>P(e'), S(e'), N(e')</tex>, где <tex>e'</tex> {{---}} линеаризованное регулярное выражение. <tex>P(e')</tex> {{---}} множество символов, с которых начинается слово из <tex>L(e')</tex>. <tex>S(e')</tex> {{---}} множество символов, на которые оканчивается слово из <tex>L(e')</tex> и <tex>N(e')</tex> {{---}} множество пар символов, которые встречаются в слове из <tex>L(e')</tex>. Более формально: <br><tex>P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}</tex>,<br><tex>S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}</tex>,<br><tex>N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}</tex>.
3. * Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>.
4. * Вычисление локального языка с заданными множествами и построение по нему автомата.
5. * Делинеаризация, переименование каждого символа из <tex>B</tex> в соответствующий ему символ из <tex>A</tex>.
===Пример работы===
