Регулярное выражение для DFA
Предпосылка – Введение конечных автоматов
Полезность . Чтобы построить 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.
- nullable(n) истинен для узла синтаксического дерева n тогда и только тогда, когда регулярное выражение, представленное n, имеет € на своем языке.
- firstpos(n) дает набор позиций, которые могут соответствовать первому символу строки, сгенерированной подвыражением с корнем n.
- 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 будет: