Что такое «регулярное выражение» для данного компьютера?

Question

Данная машина

На самом деле я запутался между двумя вариантами

1. cxa (bcxa + d) x
2. cxa (bc+ d) x

здесь «x» означает * предыдущую букву / скобку, за которой следует «x».

Answer 1

Запишите наши уравнения:

(q1) = (q1)c + (q2)b + e
(q2) = (q2)d + (q1)a

Упростите выражение для (q1), используя правило (q) = (q)x + y <=> (q) = yx*:

(q1) = ((q2)b + e)c*
(q2) = (q2)d + (q1)a

Замените выражение для (q1) в выражениедля (q2) разведите (q2) из RHS и примените правило сверху:

(q1) = ((q2)b + e)c*
(q2) = (q2)d + ((q2)b + e)c*a
     = (q2)d + (q2)bc*a + c*a
     = (q2)(d + bc*a) + c*a
     = (c*a)(d + bc*a)*

Это похоже на то, что вы использовали для варианта 1.