Строительство ТВС из РЭ

Мы можем использовать конструкцию Томпсона, чтобы найти конечный автомат из регулярного выражения. Мы сократим регулярное выражение до наименьших регулярных выражений и конвертируем их в NFA и, наконец, в DFA.

Некоторые основные выражения RA следующие:

Case 1 - Для регулярного выражения 'a' мы можем построить следующую FA -

Case 2 - Для регулярного выражения 'ab' мы можем построить следующую FA -

Case 3 - Для регулярного выражения (a + b) мы можем построить следующую FA -

Case 4 - Для регулярного выражения (a + b) * мы можем построить следующую FA -

Метод

Step 1 Создайте NFA с нулевыми перемещениями из данного регулярного выражения.

Step 2 Удалите нулевой переход из NFA и преобразуйте его в эквивалентный DFA.

Problem

Преобразуйте следующий RA в его эквивалент DFA - 1 (0 + 1) * 0

Solution

Мы объединим три выражения «1», «(0 + 1) *» и «0»

Теперь удалим εпереходы. После того, как мы удалимε переходы из NDFA, мы получаем следующее -

Это NDFA, соответствующий RE - 1 (0 + 1) * 0. Если вы хотите преобразовать его в DFA, просто примените метод преобразования NDFA в DFA, описанный в главе 1.

Конечные автоматы с нулевым ходом (NFA-ε)

Конечный автомат с нулевым ходом (FA-ε) проходит не только после ввода данных из набора алфавита, но и без какого-либо символа ввода. Этот переход без ввода называетсяnull move.

NFA-ε формально представляется 5-кортежем (Q, ∑, δ, q 0 , F), состоящим из

  • Q - конечный набор состояний

  • - конечный набор входных символов

  • δ- функция перехода δ: Q × (∑ ∪ {ε}) → 2 Q

  • q0- начальное состояние q 0 ∈ Q

  • F - набор конечных состояний / состояний Q (F⊆Q).

Над (FA-ε) принимает набор строк - {0, 1, 01}

Удаление нулевых ходов из конечных автоматов

Если в NDFA есть ϵ-ход между вершиной X и вершиной Y, мы можем удалить его, выполнив следующие шаги:

  • Найдите все выходящие из Y ребра.
  • Скопируйте все эти края, начиная с X, не меняя метки краев.
  • Если X - начальное состояние, сделайте Y также начальным состоянием.
  • Если Y - конечное состояние, сделайте X также конечным состоянием.

Problem

Преобразуйте следующий NFA-ε в NFA без нулевого перемещения.

Solution

Step 1 -

Здесь переход ε находится между q1 а также q2, так что давайте q1 является X а также qf является Y.

Здесь исходящие ребра от q f к q f для входов 0 и 1.

Step 2 -

Теперь мы скопируем все эти ребра из q 1 без изменения ребер из q f и получим следующую FA -

Step 3 -

Здесь q 1 - начальное состояние, поэтому мы делаем q f также начальным состоянием.

Итак, FA становится -

Step 4 -

Здесь q f - конечное состояние, поэтому мы делаем q 1 также конечным состоянием.

Итак, FA становится -