Я просматриваю регулярные выражения и застрял на следующем вопросе:
Укажите регулярное выражение для описания языка следующего NFA: NFA Diagram
Я не знаю, как ответить на следующий вопрос, и я не хочу, чтобы кто-то дал мне на него ответ. Если возможно, я был бы очень признателен за рекомендации о том, как решить такие вопросы или как решить эту конкретную проблему. Спасибо!
Любая помощь приветствуется!
Базовое преобразование, вы это знаете.
{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)*
ответ ipramusinto неверен. x*y((x+y)(y+xx)*xy)* принимает строку yxxyxy, которая не является решением.
проверьте соответствующие темы (комментарии) о том, как завершить.
регулярное выражение: x*y((x|y)y*x(xy*x)*y)*
