Конечный автомат сжатия

Question

У меня есть журнал выходов с учетом входных данных, например:

0 =A=> 1 =B=> 1 =B=> 0 =A=> 1 =A=> 0 =A=> 0  

И я хотел бы найти минимальный конечный автомат, представляющий его.

Я попытался вручную,разбить его на упорядоченный список переходов:

1. 0 =A=> 1
2. 1 =B=> 1
3. 1 =B=> 0
4. 0 =A=> 1
5. 1 =A=> 0
6. 0 =A=> 0

Если учесть, что существует только два состояния:

• q0 свывод 0.
• q1 с выводом 1.

Список становится:

1. q0 (0) =A=> q1 (1)
2. q1 (1) =B=> q1 (1)
3. q1 (1) =B=> q0 (0)
4. q0 (0) =A=> q1 (1)
5. q1 (1) =A=> q0 (0)
6. q0 (0) =A=> q0 (0)

Мывидно, что из состояния q0 вход A ведет к q1 в строках 1 и 4, но к состоянию q0 в строке 6. Та же проблема в состоянии q1 с действием B.Поэтому мне нужно создать два дополнительных состояния q2 с выводом 0 и q3 с выводом 1.Затем я могу переписать список следующим образом:

1. q0 (0) =A=> q1 (1)
2. q1 (1) =B=> q3 (1)
3. q3 (1) =B=> q0 (0)
4. q0 (0) =A=> q1 (1)
5. q1 (1) =A=> q2 (0)
6. q2 (0) =A=> q0 (0)

И готово.

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

Я решил рассматривать это как проблему оптимизации и использовать, например, моделируемый отжиг или генетический алгоритм, но это кажется излишним,Кроме того, я действительно чувствую, что есть простой способ сделать это, может быть, что-то, связанное с теорией графов?

Редактировать:

Благодаря комментарию @ sascha, теперь язнать, что следующий список описывает недетерминированный конечный автомат (NDFA):

1. q0 (0) =A=> q1 (1)
2. q1 (1) =B=> q1 (1)
3. q1 (1) =B=> q0 (0)
4. q0 (0) =A=> q1 (1)
5. q1 (1) =A=> q0 (0)
6. q0 (0) =A=> q0 (0)

Существуют алгоритмы для его преобразования в детерминированный конечный автомат (DFA), см. Конвертация NDFA в DFA

Я попробую это завтра, однако, я боюсь, что не получу минимальный эквивалент DFA для этого NDFA.

Answer 1

Я нашел способ сделать то, что я хочу (который работает по крайней мере в этом примере):

A. Из выходного журнала 0 =A=> 1 =B=> 1 =B=> 0 =A=> 1 =A=> 0 =A=> 0 строю список переходов:

1. q0 (0) =A=> q1 (1)
2. q1 (1) =B=> q2 (1)
3. q2 (1) =B=> q3 (0)
4. q3 (0) =A=> q4 (1)
5. q4 (1) =A=> q5 (0)
6. q5 (0) =A=> q6 (0)

B. Я преобразую его в таблицу состояний:

 q  │ A  │ B  │ Output
────┼────┼────┼────────   
 q0 │ q1 │ ── │ 0     
────┼────┼────┼────────   
 q1 │ ── │ q2 │ 1     
────┼────┼────┼────────   
 q2 │ ── │ q3 │ 1     
────┼────┼────┼────────   
 q3 │ q4 │ ── │ 0     
────┼────┼────┼────────   
 q4 │ q5 │ ── │ 1     
────┼────┼────┼──────── 
 q5 │ q6 │ ── │ 0     
────┼────┼────┼────────   
 q6 │ ── │ ── │ 0     

C. Затем я использую Процедура уменьшения Мура . Поскольку машина указана не полностью, необходимо сделать выбор.

P0 = [{q0, q1, q2, q3, q4, q5, q6}]

P1 - список состояний, сгруппированных по выходным данным: P1 = [{q0, q3, q5, q6}, {q1, q2, q4}]

P1[0] is {q0, q3, q5, q6}:

• q0(A) = q1 ∈ P1[1]
• q0(B) = ?
• q3(A) = q4 ∈ P1[1]
• q3(B) = ?
• q5(A) = q6 ∈ P1[0]
• q5(B) = ?
• q6(A) = ?
• q6(B) = ?

То есть q0 и q3 совместимы друг с другом, q5 не совместимы с ними. q6 может быть совместимо с любым из этих состояний, здесь мы выберем группу q6 с q0 и q3.

P1[1] - {q1, q2, q4}:

• q1(A) = ?
• q1(B) = q2 ∈ P1[1]
• q2(A) = ?
• q2(B) = q3 ∈ P1[0]
• q4(A) = q5 ∈ P1[0]
• q4(B) = ?

То есть q1 и q2 НЕ совместимы друг с другом. q4 может быть совместимо с любым из этих состояний, здесь мы выберем группу q4 с q1.

Итак, у нас есть P2 = [{q0, q3, q6}, {q5}, {q1, q4}, {q2}]

P2[0] is {q0, q3, q6}:

• q0(A) = q1 ∈ P2[2]
• q0(B) = ?
• q3(A) = q4 ∈ P2[2]
• q3(B) = ?
• q6(A) = ?
• q6(B) = ?

Так что q0, q3 и q6 по-прежнему совместимы друг с другом.

P2[1] is {q5}: q5 совместимо с самим собой.

P2[2] - {q1, q4}:

• q1(A) = ?
• q1(B) = q2 ∈ P2[3]
• q4(A) = q5 ∈ P2[1]
• q4(B) = ?

Так что q1 и q4 все еще совместимы друг с другом.

P2[3] is {q2}: q2 совместимо с самим собой.

Итак, у нас есть P3 = [{q0, q3, q6}, {q5}, {q1, q4}, {q2}] = P2.

Теперь у нас есть следующая таблица состояний

  q            │ A            │ B            │ Output
 ──────────────┼──────────────┼──────────────┼────────   
  {q0, q3, q6} │ {q1, q4}     │ ──────────── │ 0     
 ──────────────┼──────────────┼──────────────┼────────   
  {q1, q4}     │ q5           │ q2           │ 1     
 ──────────────┼──────────────┼──────────────┼────────   
  q2           │ ──────────── │ {q0, q3, q6} │ 1     
 ──────────────┼──────────────┼──────────────┼────────   
  q5           │ {q0, q3, q6} │ ──────────── │ 0     

И ... вуаля!

Спасибо за комментарии, они действительно помогли мне сделать правильные запросы в поисковых системах.

Редактировать: Поскольку выбор должен быть сделан, разумно предположить, что этот подход, как правило, является неоптимальным. Чтобы сделать его оптимальным, я думаю, что единственный способ - попробовать все комбинации вариантов и выбрать лучшую.