Кажется, что здесь проще создать DFA, поэтому мы можем начать с него и извлечь из него регулярное выражение.
Нам понадобится хотя бы одно начальное состояние.Это состояние не может быть принято, потому что пустая строка не начинается и не заканчивается b.Мы назовем это q0.
Если мы увидим a в этом состоянии, мы смотрим на строку, которая не начинается с b, поэтому мы не можем принять ее независимо от того, что произойдетследующий.Мы можем представить это с новым, мертвым, состоянием.Мы назовем это q1.
Если мы увидим b в q0, нам нужно новое состояние, чтобы представлять тот факт, что мы находимся на пути к тому, чтобы увидеть строку, которая соответствуеткритерии.Действительно, строка b начинается и заканчивается b и имеет четное число a (ноль - четный);так что это состояние должно приниматься.Назовите это q2.
Если мы увидим a в q2, то у нас будет нечетное число a с, и мы не видели в последний раз b, поэтому мы не можем принять строку,Однако все еще возможно принять строку из этого состояния, увидев нечетное число a с, за которым следует хотя бы один b.Позвоните штату, чтобы представить это q3.
Если мы увидим b в q2, мы окажемся в той же ситуации, что и раньше (четное число a и последний раз видели b, поэтому мы можем принять).Оставайтесь в q2.
Если в q3 и мы увидим a, теперь у нас снова четное число a и нам просто нужно b.Назовите это новое состояние q4.Если мы увидим b, нам все еще нужен a, поэтому мы могли бы также остаться в q3.
Если в q4 и мы увидим a, нам снова понадобится больше a с и может вернуться к q3.Если, с другой стороны, мы получим b, мы можем вернуться к q2, так как строка на нашем языке.
DFA выглядит так:
q s q'
-- -- --
q0 a q1 q0: initial state
q0 b q2 q1: dead state, did not begin with b
q1 a q1 q2: accepting state, even #a and start/stop with b
q1 b q2 q3: start with b, odd #a
q2 a q3 q4: start with b, even #a, stop with a
q2 b q2
q3 a q4
q3 b q3
q4 a q3
q4 b q2
Чтобы получить регулярное выражение, мы можем найти регулярные выражения, ведущие к каждому состоянию, итеративно, а затем взять объединение регулярных выражений для принятия состояний.В этом случае только q2 принимает, поэтому все, что нам нужно, это регулярное выражение для этого состояния.Мы продолжаем итеративно, подставляя на каждом этапе.
round 0
(q0): e
(q1): (q0)a + (q1)(a+b)
(q2): (q0)b + (q2)b + (q4)b
(q3): (q2)a + (q3)b + (q4)a
(q4): (q3)a
round 1
(q0): e
(q1): a + (q1)(a+b) = a(a+b)*
(q2): b + (q2)b + (q4)b = (b+(q4)b)b*
(q3): (q2)a + (q3)b + (q4)a = ((q2)+(q4))ab*
(q4): (q3)a
round 2
(q0): e
(q1): a(a+b)*
(q2): (b+(q3)ab)b*
(q3): ((q2)+(q3)a)ab* = (q2)ab* + (q3)aab* = (q2)ab*(aab*)*
(q4): (q3)a
round3:
(q0): e
(q1): a(a+b)*
(q2): (b+(q3)ab)b*
(q3): (b+(q3)ab)b*ab*(aab*)* = bb*ab*(aab*)*+(q3)abb*ab*(aab*)* = bb*ab*(aab*)*(abb*ab*(aab*)*)*
(q4): (q3)a
round4:
(q0): e
(q1): a(a+b)*
(q2): (b+bb*ab*(aab*)*(abb*ab*(aab*)*)*ab)b*
(q3): bb*ab*(aab*)*(abb*ab*(aab*)*)*
(q4): bb*ab*(aab*)*(abb*ab*(aab*)*)*a
Следовательно, регулярное выражение таково:
r = (b+bb*ab*(aab*)*(abb*ab*(aab*)*)*ab)b*
= bb* + bb*ab*(aab*)*(abb*ab*(aab*)*)*abb*
- Часть
bb* кодирует тот факт, что любая строкаb - это строка на языке. - другая часть начинается и заканчивается
bb*, что кодирует тот факт, что любая строка должна начинаться и заканчиваться b - Наиболее удаленная
a s кодируют тот факт, что любая строка в языке с a должна иметь как первую, так и последнюю a - Части
aab* допускают наличие смежных пар a - В разрешении
abb*ab* допускается наличие несмежных пар a
В качестве последнего примечания правила замены выражений, приведенные выше, следующие:
A: r r is an expression
B: As s is an expression
=
A: r
B: rs
A: r + As r, s are expressions
=
A = rs*