Множество Q состояний: {q0, q1, q2, q3, q4}.Состояния вашего эквивалентного DFA будут извлечены из набора всех подмножеств состояний из NFA, из которых 2^5 = 32.Некоторые из них могут быть недоступны, поэтому мы можем ввести только те, которых мы на самом деле достигаем.
Начальное состояние в DFA будет подмножеством состояний NFA, содержащих q0, наряду с любыми состояниями, достижимыми из q0 путем обхода.только эпсилон / лямбда переходы.Здесь начальное состояние DFA: {q0, q1}, поскольку q0 является начальным состоянием NFA, а q1 достижимо из q0, пройдя только (ровно один) эпсилон / лямбда-переход.
Теперь нам нужнопереходы, выходящие из состояния {q0, q1} для каждого символа в алфавите: a и b.Состояние, в которое {q0, q1} переходит при входе a, является подмножеством всех состояний, содержащих только те состояния, которые достижимы из q0 или q1 в NFA, путем потребления ровно одного a и прохождения произвольного числа эпсилон / лямбда-переходов.Символ a заставляет NFA переходить в q0, если он уже находится в q0, и q1 достижим из q0, пройдя переход эпсилон / лямбда;поэтому q0 и q1 будут в подмножестве, которому соответствует это следующее состояние.Поскольку q1 не переходит на a в NFA, это состояние ничего не добавляет: {q0, q1} переходит на {q0, q1} на входе a.На входе b q0 переходит в себя и q2 в NFA (и q1 также, так как q1 достижимо от q0 переходом эпсилон / лямбда).В NFA q1 переходит к q4 и q2 в NFA, поэтому эти состояния также находятся в подмножестве, которому соответствует наше состояние.Следовательно, {q0, q1} переходит к {q0, q1, q2, q4} на входе b.
Единственное состояние, с которым мы столкнулись, для которого у нас нет переходов, это {q0, q1, q2, q4}.На входе b мы можем достичь каждого из этих состояний из какого-то другого (q1, взяв переход эпсилон / лямбда после перехода к q0 из q0);но Q3 не может быть достигнуто так.Таким образом, {q0, q1, q2, q4} переходит к себе на вход b.На входе a мы можем достичь q0 (следовательно, q1) из q0;ничего из q1;и q3 (следовательно, q4 переходом эпсилон / лямбда) из q2 или q4.Следовательно, {q0, q1, q2, q4} переходит на {q0, q1, q3, q4} на входе a.
Единственное состояние, с которым мы столкнулись, для которого у нас нет переходов, это {q0, q1, q3, Q4}.На входе a убедитесь, что мы достигли того же состояния {q0, q1, q3, q4}.На входе b убедитесь, что мы достигли состояния {q0, q1, q2, q4}.
Нет состояний, для которых нам не хватает переходов.Теперь мы можем перечислить состояния, дав им более короткие имена: {q0, q1} - A;{q0, q1, q2, q4} - B;{q0, q1, q3, q4} равно C. Теперь таблица переходов выглядит следующим образом:
Q | s | Q'
===|===|===
A a A
A b B
B a C
B b B
C a C
C b B
Принимающими состояниями будут любые наши состояния, которые соответствуют подмножествам, содержащим состояния NFA, которые былипринятие в NFA: либо q3, либо q4.Оба состояния B и C содержат состояние q4, которое принимается в NFA;так что B и C принимают.Язык - это язык всех строк, которые содержат хотя бы один b.Чтобы убедиться, что это правильный язык, рассмотрим NFA.
- любая строка с хотя бы одним b должна иметь последнее вхождение b, после чего строка не содержит ничего, кроме a (или вообще ничего)), если строка заканчивается буквой b.
- , любая строка может быть использована до этой точки путем зацикливания на состоянии q0 в NFA
- , тогда переход эпсилон / лямбда может быть принят к q1
- затем последний b в строке может быть использован для перехода к q4
- с этой точки, все остальные a (если есть) могут быть использованы
- хотя бы одинb должно быть использовано для достижения q4 от q1 или до q2 для перехода к q3.
Этот DFA не является минимальным, для этого языка существует DFA с двумя состояниями:
Q | s | Q'
===|===|===
X | a | X
X | b | Y
Y | a | Y
Y | b | Y
Если X - начальное состояние, а Y - принимающее состояние, это принимает тот же язык.