Как преобразовать этот автомат в регулярное выражение через NFA - PullRequest
Новая
       96

Как преобразовать этот автомат в регулярное выражение через NFA

0 голосов
/ 28 марта 2019

Мне нужно преобразовать этот конечный автомат в регулярные выражения путем преобразования DFA (детерминированные конечные автоматы) в общий NFA (недетерминированные конечные автоматы). Как это сделать? Будут ли диаграммы состояний NFA и DFA идентичны?

DFA Picture

Ответы [ 3 ]

0 голосов
/ 29 марта 2019

Википедия ссылается на этот курс PDF: Вторая часть эквивалентности регулярных выражений с конечными автоматами , и согласно этому документу процедура начинается с этого начального шага:

A DFAпреобразуется в GNFA специальной формы с помощью следующей процедуры:

  1. Добавьте новое начальное состояние со стрелкой \ epsilon к старому начальному состоянию и новое состояние принятия со стрелкой \ epsilon от все старые принимаемые состояния.

(выделено мной)

Таким образом, NFA и DFA не будут идентичны.Это также объясняет, как работать с несколькими принимающими государствами.

0 голосов
/ 30 марта 2019

НЕТ, диаграммы состояний NFA и DFA не будут идентичны в процессе преобразования.

Для второго регулярного выражения FSM будет - ε U (aUb) a b (bUa (aUb) a b) * (εUa)

Вы можете обратиться к этимшаги -

Вот пример - это скриншоты из PDF-версии книги - «Введение в теорию вычислений» Майкла Сипсера.

0 голосов
/ 28 марта 2019

Итак, на рисунке два DFA, поэтому я покажу, как получить RE для каждого из них по очереди.Для первого мы запишем некоторые уравнения: 

(q1) = (q1)a + (q2)b + e
(q2) = (q1)b + (q2)a

Теперь мы можем использовать правило (q) = (q)x + y <=> (q) = yx* для каждого: 

(q1) = ((q2)b + e)a*
(q2) = (q1)ba*

Теперь мы можем заменить, и так как мы заботимся о(q2) мы могли бы также получить это непосредственно: 

(q2) = ((q2)b + e)a*ba*
     = (q2)ba*ba* + a*ba*
     = a*ba*(ba*ba*)*

Мы получаем регулярное выражение a*ba*(ba*ba*)*, которое, на первый взгляд, кажется правильным.Как мы получили уравнения?Для каждого штата мы записали способы «добраться до» штата и объединили их с + (или, union).Мы включаем пустую строку e в уравнение (q1), так как (q1) является начальным состоянием и ничего не нужно использовать, чтобы попасть туда (изначально).

Для второго уравнения выглядят так:

(q1) = (q3)a + e
(q2) = (q1)(a + b) + (q2)a + (q3)b
(q3) = (q2)b

Мы можем использовать наше правило, чтобы исключить самоссылку для (q2): 

(q1) = (q3)a + e
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = (q2)b

Теперь мы подставим и снова используем правило: 

(q1) = (q3)a + e
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = ((q1)(a + b) + (q3)b)a*b
     = (q1)(a + b)a*b + (q3)ba*b
     = (q1)(a + b)a*b(ba*b)*

Теперь мы снова подставляем и снова используем правило: 

(q1) = (q1)(a + b)a*b(ba*b)*a + e
     = e((a + b)a*b(ba*b)*a)*
     = ((a + b)a*b(ba*b)*a)*
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = (q1)(a + b)a*b(ba*b)*

Теперь мы можем подставить обратно, чтобы получить выражение для (q3): 

(q1) = ((a + b)a*b(ba*b)*a)*
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = ((a + b)a*b(ba*b)*a)*(a + b)a*b(ba*b)*

Регулярное выражение будетобъединение выражений для (q1) и (q3), поскольку они являются принимающими состояниями: 

r = ((a + b)a*b(ba*b)*a)* + ((a + b)a*b(ba*b)*a)*(a + b)a*b(ba*b)*
  = ((a + b)a*b(ba*b)*a)*(e + (a + b)a*b(ba*b)*)

Первая часть этого возвращает вас из состояния q1 обратно в состояние q1 всеми возможными способами;вторая часть говорит, что вы можете остаться в q1 или заняться другим делом, что в противном случае приведет к q3.

...