Строительство ТВС из РЭ
Мы можем использовать конструкцию Томпсона, чтобы найти конечный автомат из регулярного выражения. Мы сократим регулярное выражение до наименьших регулярных выражений и конвертируем их в 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 становится -