Базовое преобразование, вы знаете, что.
{q0, x, q0} becomes x*
{q0, x, q1} becomes x
{q0, x, q1}, {q0, y, q1} becomes x+y
Ваша диаграмма - DFA.Ваше самое правое государство не должно быть q1.У вас есть двойной q1.Назовите самое правильное состояние q3 с этого момента.
Я думаю, что самая трудная часть заключается в том, что происходит исходящий переход из q3 обратно в q1 и q2.
Мы начнем с левой части.
{q0, x, q0},{q0, y, q1} => x*y
q0 - начальное состояние, q1 - конечное состояние.Тогда x*y всегда должно происходить.Остальное может случиться или нет, потому что есть переход обратно на q1 с q3.Итак, мы можем написать так:
RE = x*y( ... )*
Мы сейчас работаем в скобках.
{q1, x, q2}, {q1, y, q2} => (x+y)
Поскольку есть переход обратно к q2 из q3, мыможно написать:
RE = x*y((x+y)( ... ))*
Поскольку существует только один переход для достижения конечного состояния, т.е. {q3, y, q1}, тогда мы ставим y в конце.
RE = x*y((x+y)( ... )y)*
Последняя часть исбивающая с толку часть: {q2, y, q2}, {q2, x, q3}, {q3, x, q2} => (y+xx)*x
Объяснение:
Мы находимся на q2, и у нас есть y* или (xx)* один или несколько раз, чтобы вернуться к q2.Мы можем написать (y*+(xx)*)* или просто (y+xx)*.Помните, что мы должны быть на q3, чтобы перейти в конечное состояние, читая y, затем с q2 нам нужно прочитать x, чтобы (y+xx)*x.
Итак, полное регулярное выражение: x*y((x+y)(y+xx)*xy)*