Алгоритм Глушкова

Сложность
Легкий 25%

Алгоритм Глушкова

Алгоритм Глушкова строит автомат недетерминированный, принимающий набор слов, описываемый регулярным выражением. Количество состояний автомата пропорционально размеру выражения.

Основные шаги алгоритма Глушкова, начиная с рационального выражения E, следующие:

  1. Преобразуйте выражение E в новое выражение E', где каждая буква встречается не более одного раза в E'.
  2. Постройте автомат A', принимающий набор слов, описанный E'
  3. Преобразуйте A' в автомат A, принимающий набор слов, описанный E, заменив уникальные символы E' символами происхождения

Шаг 1: отдельные буквы

Первый шаг алгоритма Глушкова состоит в том, чтобы сделать все буквы в выражении различимыми. Каждое вхождение одной и той же буквы нумеруется. Выражение E = (ab + b)* становится, например, E' = (ab0 + б1)*.

Возьмем более длинный пример: E = (a + b)*(abb + ε). После переименования имеем следующее выражение: (x1 +х2)*(Икс3Икс4Икс5 +ε).

Теперь мы должны определить группу Premier, содержащую символы, которые могут начинать слово. Последняя группа, содержащая символы, которыми может заканчиваться слово. И следующая таблица, определяющая символы, которые могут быть суффиксами другого символа.

В этом примере мы имеем:

  • Прайм = {х1,Икс2,Икс3}
  • Последний = {х1,Икс2,Икс5}
  • Таблица следующего: Алгоритм Глушкова

Шаг 2: построение автомата

Пусть E' будет регулярным выражением, в котором все буквы разные. Построим автомат A' следующим образом.

  • Набор состояний равен Q = {i} ∪ {a : a появляется в E'}
  • Начальное состояние - это состояние i
  • Конечными состояниями являются Last(E'), к которым мы добавляем i, если ε ∈ E'
  • Переходами являются (i,a,a) для a ∈ First(E') и (a,b,b) для (a,b) ∈ Next(E').

В нашем выражении (x1 +х2)*(Икс3Икс4Икс5 + ε), построим начальное состояние i с переходом x1,Икс2,Икс3 в соответствующие состояния x1, Икс2, Икс3.

Затем мы используем следующую таблицу для создания связей типа (a,b,b). Например, если мы возьмем первую строку, у нас будут следующие дуги: (x1,Икс1,Икс1), (Икс1,Икс2,Икс2), (Икс1,Икс3,Икс3).

Наконец, мы добавляем терминальные состояния {x1,Икс2,Икс5}. Это, наконец, дает следующий автомат:

Алгоритм Глушкова

Делиться
ru_RURU