Lets_Study №1 Как преобразовать регулярное выражение в конечный автомат

Перед началом:

Так как образовательная платформа нашего вуза не работает по непонятным мне причинам, я начну с самого конца.

Будет много непонятных на первый взгляд определений, но, думаю, суть алгоритма уловить получится.

Минимальная теория:

Условимся называть Регулярное выражение - РВ. А конечный автомат - КА.

Известно, что можно строить разные РВ и для этих РВ существуют свои КА. Существует теоремка как раз про это.

Теорема

Для любого РВ существует эквивалентный ему КА.

Эквивалентность тут заключается в том, что РВ и КА задают один и тот же язык.

Наглядный пример таких РВ и КВ:

Слева мы выдим само РВ, а справа мы видим эквивалентный ему КА.

Ещё небольшие условности:

Будем обозначать R, как РВ и эквивалентный ему КА.

Из контекста будет понятно, R - это РВ или КА.

Если R - это КА, то его мы будем представлять так:

Просто кружочек - это начальное состояние КА. Кружочек в кружочке - заключительное состояние КА. Внутри R.

Алгоритм Томпсона:

Алгоритм преобразования РВ в КА называется - Алгоритм Томпсона.

Мы просто следуем определению РВ:

Построим шаблоны в КА базиса и индукции:

Базис:

Индукция:

Следует отметить несколько важных примечаний:

1. КА имеет только одно заключительное состояние.
2. Не существует дуг, входящих в начальное состояния.
3. Не существует дуг, исходящих из конечного состояния.

Пример:

Нам нужно преоразовать РВ (R = (a | b)*abb) в КА, следуя алгоритму Томпсона.

Опять же, действую по алгоритму, мы должны построить Базис и Индукцию.

Потом, уже по Базису и Индукции, получится построить полный КА.

При построении нужно смотреть на шаблоны Базиса и Индукции.

Давайте же построим Базис и Индукцию!

Базис:

Индукция:

(1) - отсюда дуга нужна для зацикливания, как так при * может идти повторение любое кол-во раз, а (2) - отсюда дуга в конечное состояние, потому что при * может быть повторение 0 раз, то есть вообще не быть.

Теперь, используя построенные Базис и Индукцию, получится построить полное РВ - (R = (a | b)*abb):

Построенный КА:

Вывод:

Теперь вы умеете в алгоритм Томпсона :З.