DFA to RE (Введение в теорию автоматов, языков и вычислений)

Question

Я некоторое время боролся с этим упражнением (3.2.3 из книги, упомянутой в названии).Вас просят преобразовать DFA в RE.Автоматы:

Я пытался получить RE, следуя алгоритму, описанному в разделе 3.2.2 (метод удаления состояния), но я неполучить тот же RE, что и JFLAP (возможно, это эквивалентно, но я не уверен, правильно ли я применяю шаги).

Первый шаг (удаление состояния s):

Второй шаг (удаление состояния r):

В результате получается RE: L = (1*+(010*1+00)(1(01)*10*1)*0)* (согласно JFLAP это (1+00(10)*0+(01+00(10)*11)(0+1(10)*11)*1(10)*0)*)

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

Answer 1

Когда вы удаляете S Вкл. q, они должны иметь цикл 10 Поскольку между S и q их цикл равен (01).

В приведенном выше примере, когда мы исключаем состояние 1, в состоянии 1 их цикл 10 Надеюсь, вы легко это поймете.