Понимание (и формирование) регулярного выражения этого конечного автомата

Question

Для приведенного выше автомата регулярное выражение, которое было дано в моем учебнике, выглядит следующим образом:

a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

У меня возникают проблемы с выводом этого ...Следующее - моя попытка:

aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

Либо я ошибаюсь, либо не могу упростить это до формы, приведенной в книге.Может кто-нибудь подсказать мне здесь, указать на ошибку или объяснить ее мне шаг за шагом?

Я действительно очень благодарен и ценю это.

Answer 1

Проверьте это.Здесь представлены три хороших алгоритмических метода ответа на подобные вопросы.Изучите один из них или все три, если у вас есть время или желание.Удаление состояний довольно интуитивно понятно, хотя мне нравится метод транзитивного замыкания Клини.

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

РЕДАКТИРОВАТЬ: ваш RE эквивалентен предоставленному.вот их сокращение к вашему:

0. a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

1. = a*(a*ba*ba*ba*)*a + a*(a*ba*ba*ba*)*a*ba*ba*ba*

2. = a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

3. = a*a + a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

4. = aa* + a*(ba*ba*ba*)*ba*ba*ba*a + a*(ba*ba*ba*)*ba*ba*ba*

5. = aa* + a*(ba*ba*ba*)*ba*ba*ba*

6. = aa* + aa*(ba*ba*ba*)*ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

7. = aa* + aa*(ba*ba*ba*)* + (ba*ba*ba*)*ba*ba*ba*

8. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

9. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

Шаг 1 правильный, так как r (s + t) = rs + rt.

Шаг 2 правильный, так как r * (r * sr*) * = r * (sr *) *.

Шаг 3 является правильным, поскольку r = r + s, если L (s) является подмножеством L (r).

Шаг 4верно, так как r * r = rr * и rs + rq * s = rs + rqq * s.

Шаг 5 правильный, так как rs + r = r.

Шаг 6 правильный, так какr * s = rr * s + s.

Шаг 7 правильный, так как rs + rqq * s = rs + rq * s.

Шаг 8 правильный, так как r = r + s, еслиL (s) является подмножеством L (r).

Шаг 9 правильный, так как r * r = rr *.

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

РЕДАКТИРОВАТЬ2: Если вы заинтересованы в такого рода вопросы, проявите некоторую любовь к новому информатике StackExchange, перейдя по этой ссылке и совершив !!!

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

Answer 2

Учебник кажется правильным. Шаг за шагом:

а * (а *

Если эта часть регулярного выражения верна (другими словами, вы действительно читаете в «а»), вы перейдете к состоянию 3. После остальной части выражения:

ба *

будет иметь вас в состоянии 2,

ба *

в состоянии 4 и

ба *

вернет вас в состояние 3.

Теперь предположим, что вы не читали 'a' во время a*(a*, чтение следующего b переместит вас в состояние 2. Затем вы окажетесь в точно такой же ситуации, как и ранее, и, следуя отдых a*ba*ba*) вы в конечном итоге в состоянии 3.

Поскольку теперь вы вернулись в состояние 3, деталь (a*ba*ba*ba*)* может выполняться столько раз, сколько она хочет, поскольку это будет просто так же, как и в нашем первом сценарии (где вы читаете в «а» во время a*(a* ).

Вторая часть просто снова объясняет первый сценарий, где вы должны прочитать хотя бы одно «а», а затем все остальное - то же самое.

Надеюсь, это поможет, дайте мне знать, если это все еще не имеет смысла. Не знаю, слишком ли мое объяснение слишком ясное.