Конвертировать DFA в RE

Question

Я построил конечные автоматы для языка L всех строк, состоящих из символов 0, 1 и 2 (Σ = {0, 1, 2}), где последний символ не является меньше, чем первый символ. Например, строки 0, 2012, 01231 и 102 на языке, но 10, 2021 и 201 не на языке.

Затем из этого GNFA, чтобы я мог преобразовать в RE.

Мой RE выглядит так:

(0(0+1+2)* )(1(0(1+2)+1+2)* )(2((0+1)2+2))*)

Я понятия не имею, правильно ли это, так как я думаю, что понимаю RE, но не совсем уверен.

Может кто-нибудь сказать, если это правильно а если нет то почему?

Answer 1

Вы можете использовать алгоритм, но этот DFA может быть достаточно простым для преобразования как разовое.

Во-первых, обратите внимание, что если первый символ, видимый в исходном состоянии, - 0, вы переходите к укажите A и оставайтесь там. A принимает. Это означает, что любая строка, начинающаяся с 0, принимается. Таким образом, в нашем регулярном выражении также может быть термин, подобный 0(0+1+2)*.

Во-вторых, обратите внимание, что если первый символ, видимый в исходном состоянии, - 1, вы переходите в состояние B и остаются в состояниях B и D с этого момента. Вы покидаете B, только если видите 0 и остаетесь вне B до тех пор, пока продолжаете видеть 0. Единственный способ закончить на D - если последний символ, который вы видели, был 0 Поэтому строки, начинающиеся с 1, принимаются тогда и только тогда, когда строки не заканчиваются на 0. В нашем регулярном выражении также может присутствовать термин типа 1(0+1+2)*(1+2).

В-третьих, обратите внимание, что если первый символ, видимый в исходном состоянии, - 2, вы переходите в состояние * 1026. * и с этого момента оставайтесь в состояниях C и E. Вы выходите из состояния C, если видите что-либо, кроме 2, и оставаетесь вне B, пока не увидите 2 снова. Единственный способ получить C - это последний символ, который вы видели 2. Поэтому строки, начинающиеся с 2, принимаются тогда и только тогда, когда строки заканчиваются на 2. В нашем регулярном выражении также может быть термин, подобный 2(0+1+2)*(2), чтобы охватить эти случаи.

Наконец, мы видим, что нет других рассматриваемых случаев; наши три термина охватывают все случаи, и их объединение полностью описывает наш язык:

0(0+1+2)* + 1(0+1+2)*(1+2) + 2(0+1+2)*2

Здесь легко было просто написать ответ, потому что этот DFA подобен трем простым DFA, объединенным с началом штат. Более сложные DFA могут быть проще преобразовать в RE с использованием алгоритмов, которые не требуют от вас понимания или следования действиям DFA.

Обратите внимание, что если состояние запуска принимается (упомянуто в комментарии к другому ответу) RE изменяется следующим образом:

e + 0(0+1+2)* + 1(0+1+2)*(1+2) + 2(0+1+2)*2

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

Answer 2

Существует общий метод для преобразования любого DFA в регулярное выражение, и, вероятно, это то, что вам следует использовать для решения этой проблемы с домашним заданием.

Специально для вашей попытки вы можете Скажите, является ли RE неправильным, найдя слово, которое должно быть на языке, но которое RE не принимает, или слово, которое не должно быть на языке, который принимает RE. В этом случае строка 1002 должна быть на языке, но RE не соответствует ей.

Существует две основные причины, по которым эта строка не соответствует. Во-первых, между тремя основными частями языка должно быть объединение, а не соединение (слова, начинающиеся с 0, 1 и 2 соответственно:

(0(0+1+2)*)   (1(0(1+2)+1+2)*)   (2((0+1)2+2))*) // wrong
(0(0+1+2)*) + (1(0(1+2)+1+2)*) + (2((0+1)2+2))*) // better

Второе проблема состоит в том, что в случаях 1 и 2 цифры, меньшие, чем начальная ди git, должны повторяться:

(1(0 (1+2)+1+2)*) // wrong
(1(0*(1+2)+1+2)*) // better

Если вы сделаете обе эти вещи, RE будет Правильно. Я оставлю это в качестве упражнения для вас, чтобы выполнить этот шаг для случая 2.

Следующее, что вы можете попробовать, это найти способ сделать RE более компактным:

(1(0*(1+2)+1+2)*) // verbose
(1(0*(1+2))*) // equivalent, but more compact

Этот последний шаг является просто вопросом предпочтения. Вам не нужен конечный +1+2, потому что 0* может иметь нулевую длину, поэтому 0*(1+2) охватывает случай +1+2.