Регулярное выражение над языком C={a,b}

Кажется, здесь проще создать 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, так как строка на нашем языке.

ДФА выглядит так:

 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*

1. Часть bb* кодирует тот факт, что любая строка b является строкой языка.
2. другая часть начинается и заканчивается на bb*, что означает, что любая строка должна начинаться и заканчиваться на b
3. Самые внешние a кодируют тот факт, что любая строка на языке с a должна иметь как первое, так и последнее a.
4. Части aab* позволяют иметь смежные пары a
5. Часть 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*

Добрый вечер ! проверить это

б(аа)*б

это приводит к созданию строк, начинающихся и заканчивающихся на b

и содержащие четные группы a, если любое i-e дает a, кратное 2, т.е. четное число