найти регулярное выражение для языка, принятого следующими автоматами

Question

Найти регулярное выражение для языка, принятого следующими автоматами.

1. Устранить q1

   q0: ab
   q2: ba*
   q0 to q2: b+aa
   q2 to q0 : bb
   

2. Устранить q2

   q0: ab+b+aa(ba)*
   

(не уверен, что мой путь верен)

Answer 1

Есть два правила:

1. если X -> s и Y -> rXt, то вы можете заменить последнее на Y -> rst.
2. если X -> sX | r, то вы можете заменить это на X -> s*r.

Обычная грамматика для этого DFA следующая:

(q0) -> b(q2) | a(q1) | (q3)
(q1) -> b(q0) | a(q2)
(q2) -> b(q1)
(q3) -> lambda

Мы можем начать устранять состояния. (q3) легко избавиться от:

(q0) -> b(q2) | a(q1) | lambda
(q1) -> b(q0) | a(q2)
(q2) -> b(q1)

Мы можем довольно легко избавиться от (q2):

(q0) -> bb(q1) | a(q1) | lambda
(q1) -> b(q0) | ab(q1)

Нам нужно избавиться от самореференции в произведениях для (q1):

(q0) -> (bb+a)(q1) | lambda
(q1) -> (ab)*b(q0)

Теперь мы можем избавиться от (q1):

(q0) -> (bb+a)(ab)*b(q0) | lambda

Теперь давайте избавимся от самореференции:

 (q0) -> ((bb+a)(ab)*b)*

Итак, регулярное выражение ((bb+a)(ab)*b)* должно работать. Это возвращает нас к состоянию (q0), и (q3), принимающее состояние, находится в лямбда-замыкании (q0). Использование нескольких терминов говорит о том, что мы нашли хорошее выражение.