Применение алгебраического метода Бжозовского на этом FA - PullRequest
Новая
       43

Применение алгебраического метода Бжозовского на этом FA

2 голосов
/ 14 января 2012

Ранее я задал вопрос о том, чтобы попросить помощи в преобразовании графа переходов конечного автомата в регулярное выражение:

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

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

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

, которая объясняет три алгоритмических метода поиска регулярных выражений.Интуитивно я был привлечен к Алгебраическому методу Бжозовского и попытался решить ФА, о котором я просил помощи в предыдущем посте, который упоминается вверху.

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

R1 = bR2 + aR3

R2 = aR2 + bR4

R3= aR3 + bR2 + λ

R4 = aR4 + bR3

Это правильно?Если да, то как мне поступить с заменами, так как каждый Ri будет с точки зрения Rj, где i ≠ j.

Пожалуйста, помогите: D

1 Ответ

3 голосов
/ 14 января 2012

Я возьму удар на этом ... Сначала мы уменьшим каждое уравнение, чтобы у нас не было Ri, равных выражениям, содержащим их самих ... 

R1 = bR2 + aR3
R2 = a*bR4
R3 = a*bR2 + a*
R4 = a*bR3

Теперь о заменах ... сначала удалите R4 

R2 = a*ba*bR3

Теперь мы избавляемся от R2 

R1 = ba*ba*bR3 + aR3
R3 = a*ba*ba*bR3 + a*

Мы не хотим, чтобы R3 сам по себе RHS ... 

R3 = (a*ba*ba*b)*a*

Теперь исключите R3 

 R1 = ba*ba*b(a*ba*ba*b)*a* + a(a*ba*ba*b)*a*

Это выглядит правильно, и поэтому мы можем преобразовать его в ваш. Вы должны попробовать это упражнение.

...