Автоматы для регулярного выражения

Question

У меня есть этот простой автомат:

Затем я пишу свою систему:

L0 = aL0 + bL1

L1 = bL0 + aL1 + Ɛ

Используя теорему Ардена, я могуупростите мое выражение:

L0 = a*bL1

L1 = bL0 + aL1 + Ɛ

Тогда:

L1 = b(a*bL1) + aL1 + Ɛ

L1 = b(a*b+a)L1 + Ɛ

L1 = b(a*b+a)*

Это кажется неправильным, но я не понимаю почему, может кто-то объяснить мне, где я не прав?

Answer 1

Ваша проблема в том, что L0 и L1 представляют языки строк, которые ведут к L0 и L1, а не языки строк, которые ведут от L0 и L1 к принимающему состоянию.Следовательно, пустая строка не эквивалентна L1, принимающему состоянию, но L0, начальному состоянию.Следовательно,

L0 = aL0 + bL1 + Ɛ
L1 = bL0 + aL1

Затем

L0 = a*(bL1 + Ɛ)
L1 = bL0 + aL1

След.

L0 = a*(bL1 + Ɛ)
L1 = ba*(bL1 + Ɛ) + aL1
   = ba*bL1 + ba* + aL1
   = (ba*b + a)L1 + ba*
   = (ba*b + a)*ba*

Это регулярное выражение выглядит правильным.