Регулярное выражение для DFA

Опубликовано: 6 Октября, 2022

Предпосылка – Введение конечных автоматов

Полезность . Чтобы построить DFA из заданного регулярного выражения, мы можем сначала создать NFA для данного выражения, а затем преобразовать этот NFA в DFA методом построения подмножества. Но чтобы избежать этой двухэтапной процедуры, наоборот, нужно напрямую построить DFA для данного выражения.

DFA относится к детерминированным конечным автоматам. В DFA для каждого состояния и для каждого входного символа существует одно и только одно состояние, в которое автомат может иметь переход из своего текущего состояния. DFA не допускает никаких ∈-переходов.

Чтобы построить DFA непосредственно из регулярного выражения, нам нужно выполнить шаги, перечисленные ниже:

Пример: Предположим, что задано регулярное выражение r = (a|b)*abb

1. Во-первых, мы строим дополненное регулярное выражение для данного выражения. Объединяя уникальный маркер правого конца '#' с регулярным выражением r, мы даем принимающее состояние для перехода ra на '#', что делает его важным состоянием NFA для r#.

So, r" = (a|b)*abb#

2. Затем строим синтаксическое дерево для r#.

3. Далее нам нужно оценить четыре функции, допускающие значение null, firstpos, lastpos и followpos.

  1. nullable(n) истинен для узла синтаксического дерева n тогда и только тогда, когда регулярное выражение, представленное n, имеет € на своем языке.
  2. firstpos(n) дает набор позиций, которые могут соответствовать первому символу строки, сгенерированной подвыражением с корнем n.
  3. lastpos(n) дает набор позиций, которые могут соответствовать последнему символу строки, сгенерированной подвыражением с корнем n.

Мы называем внутренний узел узлом-кошкой, узлом-или или узлом-звездой, если он помечен конкатенацией | или * соответственно.

Правила вычисления nullable, firstpos и lastpos :

Узел n обнуляемый (n) первая позиция (сущ.) последняя позиция (сущ.)
n — листовой узел с надписью € истинный
n — листовой узел, помеченный позицией i ЛОЖЬ {я} {я}
n является узлом or с левым дочерним элементом c1 и правым дочерним элементом c2 Обнуляемый (c1) или обнуляемый (c2) первая позиция (c1) ∪ первая позиция (c2) последняя позиция (c1) ∪ последняя позиция (c2)
n — это кошачий узел с левым дочерним элементом c1 и правым дочерним элементом c2. Обнуляемый (c1) и обнуляемый (c2) Если nullable(c1), то firstpos(c1) ∪ firstpos(c2) else firstpos(c1) Если nullable(c2), то lastpos(c2) ∪ lastpos(c1), иначе lastpos(c2)
n — звездный узел с дочерним узлом c1 истинный первая позиция (c1) последняя позиция (c1)

Правила вычисления фоллоупоса:

1. Если n — это cat-узел с левым дочерним элементом c1 и правым дочерним элементом c2, а i — позиция в lastpos(c1), то все позиции в firstpos(c2) находятся в followpos(i).

2. Если n — узел-звезда, а i — позиция в lastpos(n), то все позиции в firstpos(n) находятся в followpos(i).

3. Теперь, когда мы ознакомились с правилами вычисления firstpos и lastpos, переходим к вычислению их значений для синтаксического дерева заданного регулярного выражения (a|b)*abb#.

Давайте теперь вычислим следующую позицию снизу вверх для каждого узла в синтаксическом дереве.

УЗЕЛ последующие посты
1 {1, 2, 3}
2 {1, 2, 3}
3 {4}
4 {5}
5 {6}
6

4. Теперь мы создаем Dstates , набор состояний DFA D и Dtran , таблицу переходов для D. Начальное состояние DFA D — firstpos(root), а принимающие состояния — все те, которые содержат позицию, связанную с символом маркера конца # .

В нашем примере первая позиция корня равна {1, 2, 3}. Пусть это состояние будет A, и рассмотрим входной символ a. Позиции 1 и 3 предназначены для a, поэтому пусть B = followpos(1) ∪ followpos(3) = {1, 2, 3, 4}. Так как этот набор еще не виден, положим Dtran[A, a] := B.

Когда мы рассматриваем вход b, мы обнаруживаем, что из позиций в A только 2 связаны с b, поэтому мы рассматриваем множество followpos(2) = {1, 2, 3}. Поскольку этот набор уже был замечен ранее, мы не добавляем его в Dstates, а добавляем переход Dtran[A, b]:= A.

Продолжая таким же образом с остальными состояниями, мы приходим к приведенной ниже таблице переходов.

Вход
Состояние а б
⇢ А Б А
Б Б С
С Б Д
Д Б А

Здесь A — начальное состояние, а D — принимающее состояние.

5. Наконец, мы рисуем DFA для приведенной выше таблицы переходов.

Окончательный DFA будет: