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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Определения== {{Определение |definition = Состояния <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex> е...»)
 
Строка 33: Строка 33:
 
#Для всех пар <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> \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>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма. <br>
 +
Пусть существует автомат <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><br>
 +
Состояний в <tex>A'</tex> меньше чем в <tex>A_{min}</tex>, значит двум состояниям из <tex>A_{min}</tex> эквивалентно одно состояние из <tex>A'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.<br>
 +
Так как каждому состоянию из <tex>A_{min}</tex> эквивалентно состояние из <tex>A'</tex>, то автоматы <tex>A_{min}</tex> и <tex>A'</tex> изоморфны.
 +
 +
==Время работы алгоритма==
 +
Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.
 +
 +
==Пример==

Версия 22:56, 5 ноября 2011

Определения

Определение:
Состояния [math]u[/math] и [math]v[/math] различимы строкой [math]s[/math] если
  1. [math] \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle [/math], где [math]t \in T [/math]
  2. [math] \langle v, s \rangle \vdash^* \langle z, \varepsilon \rangle [/math], где [math]z \notin T [/math]


Определение:
Состояния [math]u[/math] и [math]v[/math] эквивалентны, если они неразличимы никакой строкой [math]s[/math].


Теорема:
Если [math]u[/math] и [math]v[/math], [math]v[/math] и [math]z[/math] эквивалентны, то [math]u[/math] и [math]z[/math] эквивалентны.
Доказательство:
[math]\triangleright[/math]

Пусть [math]u[/math] и [math]z[/math] неэквивалентны. Тогда [math] \mathcal {9} s[/math], такой, что

  1. [math] \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle [/math], где [math]t \in T [/math]
  2. [math] \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle [/math], где [math]t_1 \notin T [/math].

Рассмотрим [math]x[/math], такой, что [math] \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle [/math].
Если [math]x \in T[/math], то [math]v[/math] и [math]z[/math] различимы строкой [math]s[/math]. Противоречие.
Если [math]x \notin T[/math], то [math]u[/math] и [math]v[/math] различимы строкой [math]s[/math]. Противоречие.

Значит, [math]u[/math] и [math]z[/math] эквивалентны.
[math]\triangleleft[/math]

Алгоритм

Основная идея алгоритма разбить состояния на классы эквивалентности — они и будут состояниями минимального автомата. В таблице размером [math]n \times n[/math], где [math]n[/math] — количество состояний автомата будем помечать неэквивалентные состояния. Изначально добавим в очередь [math]Q[/math] пары состояний различимых строкой [math] \varepsilon [/math] и пометим их в таблице. Пока [math]Q[/math] не станет пуста, будем делать следующее:

  1. Извлечем пару [math] \langle u, v \rangle [/math] из [math]Q[/math].
  2. Для всех пар [math] \langle t, k \rangle [/math], таких, что [math] \mathcal {9} c \in \Sigma, \langle t, c \rangle \vdash \langle u, \varepsilon \rangle, \langle k, c \rangle \vdash \langle v, \varepsilon \rangle [/math] и пара [math] \langle t, k \rangle[/math] не отмечена в таблице, то отметим ее в таблице и добавим в [math]Q[/math].

За один проход по таблице согласно теореме разбиваем не помеченные состояния на классы эквивалентности.

Корректность алгоритма

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

Время работы алгоритма

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

Пример