Викиконспекты - Вклад участника [ru]

Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний

2011-11-06T01:17:16Z

Petrova: /* Алгоритм */

==Определения==
{{Определение
|definition =
Состояния <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex> если
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
# <tex> \langle v, s \rangle \vdash^* \langle z, \varepsilon \rangle </tex>, где <tex>z \notin T </tex>
}}
{{Определение
|definition =
Состояния <tex>u</tex> и <tex>v</tex> эквивалентны, если они неразличимы никакой строкой <tex>s</tex>.
}}

{{Теорема
|statement =
Если <tex>u</tex> и <tex>v</tex>, <tex>v</tex> и <tex>z</tex> эквивалентны, то <tex>u</tex> и <tex>z</tex> эквивалентны.
|proof =
Пусть <tex>u</tex> и <tex>z</tex> неэквивалентны. Тогда <tex> \mathcal {9} s</tex>, такой, что
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
# <tex> \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle </tex>, где <tex>t_1 \notin T </tex>.
Рассмотрим <tex>x</tex>, такой, что <tex> \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle </tex>. 
Если <tex>x \in T</tex>, то <tex>v</tex> и <tex>z</tex> различимы строкой <tex>s</tex>. Противоречие. 
Если <tex>x \notin T</tex>, то <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex>. Противоречие. 
Значит, <tex>u</tex> и <tex>z</tex> эквивалентны.
}}

==Алгоритм==
Основная идея алгоритма разбить состояния на классы эквивалентности — они и будут состояниями минимального автомата.
В таблице размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата будем помечать неэквивалентные состояния.
Изначально добавим в очередь <tex>Q</tex> пары состояний различимых строкой <tex> \varepsilon </tex> и пометим их в таблице.
Пока <tex>Q</tex> не станет пуста, будем делать следующее:
#Извлечем пару <tex> \langle u, v \rangle </tex> из <tex>Q</tex>.
#Для всех пар <tex> \langle t, k \rangle </tex>, таких, что <tex> \mathcal {9} c \in \Sigma, \langle t, c \rangle \vdash \langle u, \varepsilon \rangle, \langle k, c \rangle \vdash \langle v, \varepsilon \rangle </tex> и пара <tex> \langle t, k \rangle</tex> не отмечена в таблице, то отметим ее в таблице и добавим в <tex>Q</tex>.
За один проход по таблице согласно теореме разбиваем не помеченные состояния на классы эквивалентности. 
Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата. 
Терминальными состояниями полученного автомата будут состояния, соответствующие классам эквивалентности, содержащим терминальные состояния исходного автомата.

==Корректность алгоритма==
Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма. 
Пусть существует автомат <tex>A'</tex> эквивалентный <tex>A</tex>, но с числом состояний меньшим чем в <tex>A_{min}</tex>.
Стартовые состояния <tex>s \in A_{min}</tex> и <tex>s' \in A'</tex> эквивалентны, так как <tex>A_{min}</tex> и <tex>A'</tex> допускают один и тот же язык. Рассмотрим строку <tex>\alpha = a_1a_2...a_{k}</tex>, где <tex>a_{i} \in \Sigma</tex>, такую что <tex> \langle s, \alpha \rangle \vdash^* \langle u, \varepsilon \rangle </tex>, <tex> \langle s', \alpha \rangle \vdash^* \langle u', \varepsilon \rangle </tex>. Пусть <tex>\langle s, a_1 \rangle \vdash^* \langle l, \varepsilon \rangle </tex> и <tex>\langle s', a_1 \rangle \vdash^* \langle l', \varepsilon \rangle </tex>. Так как <tex>s</tex> и <tex>s'</tex> эквивалентны, то <tex>l</tex> и <tex>l'</tex> эквивалентны. Аналогично для всех <tex>a_{i}</tex>. В итоге получим, что <tex>u</tex> эквивалентно <tex>u'</tex>. Значит для каждого состояния из <tex>A_{min}</tex> существует эквивалентное состояние из <tex>A'</tex> 
Состояний в <tex>A'</tex> меньше чем в <tex>A_{min}</tex>, значит двум состояниям из <tex>A_{min}</tex> эквивалентно одно состояние из <tex>A'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие. 
Так как каждому состоянию из <tex>A_{min}</tex> эквивалентно состояние из <tex>A'</tex>, то автоматы <tex>A_{min}</tex> и <tex>A'</tex> изоморфны.

==Время работы алгоритма==
Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.

==Пример==
Минимизируем данный автомат. 
[[Файл:dka.jpg]]
 
Будем рассматривать только нижний треугольник таблицы пар различимых состояний. 
Отметили состояния, различающиеся строкой <tex>\varepsilon</tex>
{| border = "1"
|B
|
|colspan = "6"|
|-
|C
|
|
|colspan = "5"|
|-
|D
|
|
|
|colspan = "4"|
|-
|E
|
|
|
|
|colspan = "3"|
|-
|F
|x
|x
|x
|x
|x
|colspan = "2"|
|-
|G
|x
|x
|x
|x
|x
|
|colspan = "1"|
|-
|H
|
|
|
|
|
|x
|x
|-
|
|A
|B
|C
|D
|E
|F
|G
|}

На момент опустошения очереди
{| border = "1"
|B
|
|colspan = "6"|
|-
|C
|x
|x
|colspan = "5"|
|-
|D
|x
|x
|
|colspan = "4"|
|-
|E
|x
|x
|x
|x
|colspan = "3"|
|-
|F
|x
|x
|x
|x
|x
|colspan = "2"|
|-
|G
|x
|x
|x
|x
|x
|
|colspan = "1"|
|-
|H
|x
|x
|x
|x
|x
|x
|x
|-
|
|A
|B
|C
|D
|E
|F
|G
|}

Из таблицы видно, что классы эквивалентных состояний это <tex> \mathcal {f} A, B \mathcal {g}, \mathcal {f} C, D \mathcal {g}, \mathcal {f} F, G \mathcal {g}, \mathcal {f} E \mathcal {g}, \mathcal {f} H \mathcal {g} </tex>. 
Итого получили такой автомат: [[Файл:dkaMin.jpg]]

Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний

2011-11-06T01:11:57Z

Petrova:

==Определения==
{{Определение
|definition =
Состояния <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex> если
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
# <tex> \langle v, s \rangle \vdash^* \langle z, \varepsilon \rangle </tex>, где <tex>z \notin T </tex>
}}
{{Определение
|definition =
Состояния <tex>u</tex> и <tex>v</tex> эквивалентны, если они неразличимы никакой строкой <tex>s</tex>.
}}

{{Теорема
|statement =
Если <tex>u</tex> и <tex>v</tex>, <tex>v</tex> и <tex>z</tex> эквивалентны, то <tex>u</tex> и <tex>z</tex> эквивалентны.
|proof =
Пусть <tex>u</tex> и <tex>z</tex> неэквивалентны. Тогда <tex> \mathcal {9} s</tex>, такой, что
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
# <tex> \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle </tex>, где <tex>t_1 \notin T </tex>.
Рассмотрим <tex>x</tex>, такой, что <tex> \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle </tex>. 
Если <tex>x \in T</tex>, то <tex>v</tex> и <tex>z</tex> различимы строкой <tex>s</tex>. Противоречие. 
Если <tex>x \notin T</tex>, то <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex>. Противоречие. 
Значит, <tex>u</tex> и <tex>z</tex> эквивалентны.
}}

==Алгоритм==
Основная идея алгоритма разбить состояния на классы эквивалентности — они и будут состояниями минимального автомата.
В таблице размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата будем помечать неэквивалентные состояния.
Изначально добавим в очередь <tex>Q</tex> пары состояний различимых строкой <tex> \varepsilon </tex> и пометим их в таблице.
Пока <tex>Q</tex> не станет пуста, будем делать следующее:
#Извлечем пару <tex> \langle u, v \rangle </tex> из <tex>Q</tex>.
#Для всех пар <tex> \langle t, k \rangle </tex>, таких, что <tex> \mathcal {9} c \in \Sigma, \langle t, c \rangle \vdash \langle u, \varepsilon \rangle, \langle k, c \rangle \vdash \langle v, \varepsilon \rangle </tex> и пара <tex> \langle t, k \rangle</tex> не отмечена в таблице, то отметим ее в таблице и добавим в <tex>Q</tex>.
За один проход по таблице согласно теореме разбиваем не помеченные состояния на классы эквивалентности.

==Корректность алгоритма==
Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма. 
Пусть существует автомат <tex>A'</tex> эквивалентный <tex>A</tex>, но с числом состояний меньшим чем в <tex>A_{min}</tex>.
Стартовые состояния <tex>s \in A_{min}</tex> и <tex>s' \in A'</tex> эквивалентны, так как <tex>A_{min}</tex> и <tex>A'</tex> допускают один и тот же язык. Рассмотрим строку <tex>\alpha = a_1a_2...a_{k}</tex>, где <tex>a_{i} \in \Sigma</tex>, такую что <tex> \langle s, \alpha \rangle \vdash^* \langle u, \varepsilon \rangle </tex>, <tex> \langle s', \alpha \rangle \vdash^* \langle u', \varepsilon \rangle </tex>. Пусть <tex>\langle s, a_1 \rangle \vdash^* \langle l, \varepsilon \rangle </tex> и <tex>\langle s', a_1 \rangle \vdash^* \langle l', \varepsilon \rangle </tex>. Так как <tex>s</tex> и <tex>s'</tex> эквивалентны, то <tex>l</tex> и <tex>l'</tex> эквивалентны. Аналогично для всех <tex>a_{i}</tex>. В итоге получим, что <tex>u</tex> эквивалентно <tex>u'</tex>. Значит для каждого состояния из <tex>A_{min}</tex> существует эквивалентное состояние из <tex>A'</tex> 
Состояний в <tex>A'</tex> меньше чем в <tex>A_{min}</tex>, значит двум состояниям из <tex>A_{min}</tex> эквивалентно одно состояние из <tex>A'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие. 
Так как каждому состоянию из <tex>A_{min}</tex> эквивалентно состояние из <tex>A'</tex>, то автоматы <tex>A_{min}</tex> и <tex>A'</tex> изоморфны.

==Время работы алгоритма==
Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.

==Пример==
Минимизируем данный автомат. 
[[Файл:dka.jpg]]
 
Будем рассматривать только нижний треугольник таблицы пар различимых состояний. 
Отметили состояния, различающиеся строкой <tex>\varepsilon</tex>
{| border = "1"
|B
|
|colspan = "6"|
|-
|C
|
|
|colspan = "5"|
|-
|D
|
|
|
|colspan = "4"|
|-
|E
|
|
|
|
|colspan = "3"|
|-
|F
|x
|x
|x
|x
|x
|colspan = "2"|
|-
|G
|x
|x
|x
|x
|x
|
|colspan = "1"|
|-
|H
|
|
|
|
|
|x
|x
|-
|
|A
|B
|C
|D
|E
|F
|G
|}

На момент опустошения очереди
{| border = "1"
|B
|
|colspan = "6"|
|-
|C
|x
|x
|colspan = "5"|
|-
|D
|x
|x
|
|colspan = "4"|
|-
|E
|x
|x
|x
|x
|colspan = "3"|
|-
|F
|x
|x
|x
|x
|x
|colspan = "2"|
|-
|G
|x
|x
|x
|x
|x
|
|colspan = "1"|
|-
|H
|x
|x
|x
|x
|x
|x
|x
|-
|
|A
|B
|C
|D
|E
|F
|G
|}

Из таблицы видно, что классы эквивалентных состояний это <tex> \mathcal {f} A, B \mathcal {g}, \mathcal {f} C, D \mathcal {g}, \mathcal {f} F, G \mathcal {g}, \mathcal {f} E \mathcal {g}, \mathcal {f} H \mathcal {g} </tex>. 
Итого получили такой автомат: [[Файл:dkaMin.jpg]]

Файл:DkaMin.jpg

2011-11-06T01:03:22Z

Petrova: Минимизированный автомат

Минимизированный автомат

Файл:Dka.jpg

2011-11-06T01:02:04Z

Petrova: Автомат для минимизации

Автомат для минимизации