Я считаю, что создание регулярных выражений сложнее, чем DFA, поэтому я рекомендую сначала создавать DFA, а затем получать регулярные выражения.
(a) Мы можем создать DFA, который обнаружит подстроку 00 и перейдет кмертвое состояние.
q s q'
-- -- --
q0 0 q1 q0 is the initial state
q0 1 q0 q0 and q1 are accepting
q1 0 q2 q2 is a dead state
q1 1 q0
q2 0 q2
q2 1 q2
Чтобы получить регулярное выражение, мы итеративно находим для каждого состояния регулярное выражение для строк, ведущих к этому состоянию.Затем мы берем объединение всех регулярных выражений для принимающих состояний.
iteration 1
q0: e + (q0)1 + (q1)1
q1: (q0)0
q2: (q1)0 + (q2)0 + (q2)1
iteration 2
q0: e + (q0)1 + (q0)01
q1: (q0)0
q2: (q0)00 + (q2)0 + (q2)1
iteration 3
q0: e+(1+01)*
q1: (e+(1+01)*)0
q2: (e+(1+01)*)00(0+1)*
Поскольку q0 и q1 являются принимающими состояниями, регулярное выражение имеет вид
e+(1+01)*+(e+(1+01)*)0
= (1+01)*+(1+01)*0 // e + r* = r*
= (1+01)*e+(1+01)*0 // r = re
= (1+01)(e+0) // distributive law of concatenation
(b) DFA здесьэто:
q s s'
-- -- --
q0 0 q1
q0 1 q1 q0 is the initial state
q1 0 q2 q3 is the accepting state
q1 1 q2
q2 0 q3
q2 1 q3
q3 0 q3
q3 1 q3
То же упражнение:
iteration 1
q0: e
q1: (q0)0 + (q0)1
q2: (q1)0 + (q1)1
q3: (q2)0 + (q2)1
iterations 2-3 (combined)
q0: e
q1: e0 + e1
q2: (0+1)0 + (0+1)1
q3: (q2)0 + (q2)1 + (q3)0 + (q3)1
iteration 4
q0: e
q1: e0 + e1
q2: (0+1)0 + (0+1)1
q3: ((0+1)0 + (0+1)1)(0+1)(0+1)*
Поскольку q4 является единственным принимающим состоянием, ответ просто
((0+1)0 + (0+1)1)(0+1)(0+1)*
= (00+10+01+11)(0+1)(0+1)*
(c) Это оченьаналогично (a) за исключением того, что мы выбрасываем строки, заканчивающиеся на 0. То есть q1 не принимает.Таким образом, DFA такой же, как в (a), с q1 не принимает, и поэтому регулярное выражение просто e+(1+01)* = (1+01)*.
(d) A DFA:
q s q'
-- -- --
q0 0 q1
q0 1 q2 q0 is the initial state
q1 0 q1 q3 is the accepting state
q1 1 q1 q1 is the dead state
q2 0 q1 q0,q1,q2 ensure the string starts with 11
q2 1 q3 q3,q4,q5 ensure the string stops with 11
q3 0 q4
q3 1 q3
q4 0 q4
q4 1 q5
q5 0 q4
q5 1 q3
Конечно, мы можем выполнить то же упражнение, что и выше, но на самом деле регулярное выражение здесь легко сделать: 11+111+11(0+1)*11.
(e) DFA:
q s q'
-- -- --
q0 0 q1
q0 1 q2 q0 is the initial state
q1 0 q0 q3 is the accepting state
q1 1 q3 q0: #0 and #1 are even
q2 0 q3 q1: #0 is odd, #1 is even
q2 1 q0 q2: #0 is even, #1 is odd
q3 0 q2 q3: #0 is odd, #1 is odd
q3 1 q1
Регулярное выражение здесьсложно и оставлено в качестве упражнения.Вы можете пройти через итерации, как в предыдущих примерах;просто запомните правило:
qx: r + (qx)s ---> qx: (r)(s*)
Затем просто удаляйте один символ за раз, пока у вас не появится регулярное выражение для (q3) без заполнителей состояний.Удачи.