1632
правки
Изменения
м
==Определения=={{ОпределениеЗадача
Состояния <tex>u</tex> и <tex>v</tex> '''различимы строкой''' <tex>s</tex>, если# Пусть дан [[Детерминированные_конечные_автоматы | автомат]] <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle mathcal{A}</tex>, где . Требуется построить автомат <tex>t \in T mathcal{A}_{min}</tex>с наименьшим количеством состояний,# <tex> \langle vраспознающий тот же язык, s \rangle \vdash^* \langle z, \varepsilon \rangle что и </tex>, где <tex>z \notin T </tex>.mathcal{A}}{{Определение|definition = Состояния <tex>u</tex> и <tex>v</tex> '''эквивалентны''', если они не различимы никакой строкой.
{{Теорема|statement =Введённое выше отношение является [[Транзитивное отношение#Отношение эквивалентности. Класс эквивалентности|отношением эквивалентности]].|proof = * В исходном автомате мы имели <oltex>n<li/tex> состояний с номерами от <tex>u \thicksim u0</tex> — очевидно. до </litex>n - 1<li/tex> . Удобно будет увеличить все номера состояний на <tex>u\thicksim v \Rightarrow v\thicksim u1</tex> — очевидно. и добавить в исходный автомат вершину </litex>0<li/tex> , в которую будут вести по умолчанию все переходы по всем символам (в том числе переходы по всем символам в эту вершину из неё самой), которых не было в исходном автомате, тем самым увеличив количество состояний <tex>u\thicksim v, v\thicksim z \Rightarrow u\thicksim zn</tex>. Пусть на <tex>u1</tex> и . Теперь стартовое состояние будет иметь номер <tex>z1</tex> неэквивалентны. Тогда * '''Шаг 1'''. Построим множество <tex> \mathcal delta^{9-1} s</tex> такая, чтов котором будем хранить списки обратных ребер.<ol>* '''Шаг 2'''. Найдем все достижимые состояния из стартового. Например, с помощью [[Обход_в_глубину,_цвета_вершин | обхода в глубину]].<li>* '''Шаг 3'''. Добавим в очередь <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle Q</tex>пары состояний, где различимых строкой <tex>t \in T varepsilon </tex>, </li>и пометим их в таблице.<li>* '''Шаг 4'''. Для каждой непомеченной пары <tex> \langle zu, s \rangle \vdash^* \langle t_1, \varepsilon v \rangle </tex>нужно проверить, где что <tex>t_1 \notin T </tex>. </li></ol>Рассмотрим <tex>xexists c \in \Sigma</tex> такой, что пара <tex> \langle v\delta(u, c), s \rangle \vdash^* \langle xdelta(v, \varepsilon c) \rangle </tex>помечена. <br />Если Тогда мы можем пометить пару <tex>x \in Tlangle u, v \rangle </tex>, то .: Пока <tex>vQ</tex> и не станет пуста, будем делать следующее:: 1. Извлечем пару <tex>z\langle u, v \rangle </tex> различимы строкой из <tex>sQ</tex>. Противоречие: 2. <br />Если Для каждого символа <tex>x c \notin Tin \Sigma</tex>, то перебираем пары состояний <tex>\langle \delta^{-1}(u</tex> и <tex>, c), \delta^{-1}(v</tex> различимы строкой <tex>s,c) \rangle</tex>. ПротиворечиеЕсли находим ещё непомеченную пару, то помечаем её в таблице и кладем в очередь. <br />Значит: В момент опустошения очереди пары состояний, не помеченные в таблице, <tex>u</tex> являются парами эквивалентных состояний. * '''Шаг 5'''. За один проход по таблице разбиваем пары эквивалентных состояний на классы эквивалентности.* '''Шаг 6'''. За один проход по списку классов эквивалентности выделяем список новых состояний и <tex>z</tex> эквивалентныпереходов между ними.</li> </ol>}}Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата.
==Алгоритм==
Основная идея алгоритма заключается в том, чтобы разбить состояния на классы эквивалентности — они и будут состояниями минимизированного автомата. <br />
Для реализации алгоритма нам потребуются очередь <tex>Q</tex> и таблица размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. <br />
Будем помечать в таблице пары неэквивалентных состояний и класть их в очередь. <br />
Изначально добавим в очередь <tex>Q</tex> пары состояний, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.
Пока <tex>Q</tex> не станет пуста, будем делать следующее:
#Извлечем пару <tex> \langle u, v \rangle </tex> из <tex>Q</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> не отмечена в таблице.
В момент опустошения очереди пары состояний, не помеченные в таблице, являются парами эквивалентных состояний.
За один проход по таблице, согласно теореме, разбиваем пары эквивалентных состояний на классы эквивалентности. <br />
Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата. <br />
На момент опустошения очереди:{| 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 |}* [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
Из таблицы видно==Источники информации==* ''Хопкрофт Д., что классы эквивалентных состояний это <tex> \mathcal {f} AМотвани Р., B \mathcal {g}Ульман Д.'' Введение в теорию автоматов, \mathcal {f} Cязыков и вычислений, D \mathcal {g}2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», \mathcal 2002. — С. 171 - 182. — ISBN 5-8459-0261-4* [[wikipedia:ru:DFA_minimization | Wikipedia {f} F, G \mathcal {g---}, \mathcal {f} E \mathcal {g}, \mathcal {f} H \mathcal {g} <DFA minimization]]* [http://tex>www.eecs.berkeley. <br edu/~sseshia/172/lectures/>Lecture6.pdf Sanjit A. Seshia, "Minimization of DFAs"]Итого получили такой автомат* [http: <br /> [[Файл:dkaMin/www.comp.nus.edu.sg/~cs4212/dfa-min.jpg]pdf National University of Singapore, "DFA Minimization"]
==Источники==[[Категория: Теория формальных языков]]''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков [[Категория: Автоматы и вычислений, 2-е издание. Пер. с англ. — М.регулярные языки]][[Категория: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4Минимизация ДКА ]]
rollbackEdits.php mass rollback
|definition =
}}
==Алгоритм==
=== Описание ===
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности | классы эквивалентности]] — они и будут состояниями минимизированного автомата.
Для реализации алгоритма нам потребуются [[Очередь | очередь]] <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА | неэквивалентных состояний]] и класть их в очередь.
Терминальными состояниями полученного автомата будут состояния, соответствующие классам эквивалентности, содержащим терминальные состояния исходного автомата.
===Корректность алгоритма===Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_\mathcal{A}_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма. <br /> Пусть существует автомат <tex>\mathcal{A}'</tex>, эквивалентный <tex>\mathcal{A}</tex>, но с числом состояний меньшим, чем в <tex>A_\mathcal{A}_{min}</tex>.Стартовые состояния <tex>s \in A_\mathcal{A}_{min}</tex> и <tex>s' \in \mathcal{A}'</tex> эквивалентны, так как <tex>A_\mathcal{A}_{min}</tex> и <tex>\mathcal{A}'</tex> допускают один и тот же язык. Рассмотрим строку <tex>\alpha = a_1a_2...\ldots 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_\mathcal{A}_{min}</tex> существует эквивалентное состояние из <tex>\mathcal{A}'</tex>.<br /> Состояний в <tex>A'</tex> меньше, чем в <tex>A_\mathcal{A}_{min}</tex>, значит двум состояниям из <tex>A_\mathcal{A}_{min}</tex> эквивалентно одно состояние из <tex>\mathcal{A}'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_\mathcal{A}_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.<br /> Так как каждому состоянию из <tex>A_\mathcal{A}_{min}</tex> эквивалентно состояние из <tex>\mathcal{A}'</tex>, то автоматы <tex>A_\mathcal{A}_{min}</tex> и <tex>\mathcal{A}'</tex> изоморфны. == Псевдокод ==Функция для построения таблицы неэквивалентности. '''boolean'''[][] buildTable('''int''' n, '''boolean'''[] isTerminal, '''vector'''[][] <tex>\delta^{-1}</tex>): '''queue''' Q '''boolean''' marked[n][n] <font color="green">// Шаг 3</font> '''for''' i = 0<tex>\ldots</tex>n - 1 '''for''' j = 0<tex>\ldots</tex>n - 1 '''if''' '''not''' marked[i][j] '''and''' isTerminal[i] != isTerminal[j] marked[i][j] = marked[j][i] = ''true'' Q.push(<tex>\langle i, j \rangle</tex>) <font color="green">// Шаг 4</font> '''while''' '''not''' Q.isEmpty() <tex>\langle u, v \rangle</tex> = Q.poll() '''for''' c <tex>\in</tex> <tex>\Sigma</tex> '''for''' r <tex>\in</tex> <tex>\delta^{-1}</tex>[u][c] '''for''' s <tex>\in</tex> <tex>\delta^{-1}</tex>[v][c] '''if''' '''not''' marked[r][s] marked[r][s] = marked[s][r] = ''true'' Q.push(<tex>\langle r, s \rangle</tex>) '''return''' marked Основная функция алгоритма. '''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>): <font color="green">// Шаг 1</font> Построим таблицу списков обратных ребер {{---}} <tex>\delta^{-1}</tex> размером <tex>n \times |\Sigma|</tex>. <font color="green">// Шаг 2</font> Построим массив достижимости состояний из стартового {{---}} reachable размером <tex>n</tex>. <font color="green">// Шаги 3 и 4</font> '''boolean'''[][] marked = buildTable(n, isTerminal, <tex>\delta^{-1}</tex>) <font color="green">// Шаг 5</font> '''int'''[] component[n] <font color="green">// По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.</font> fill(component, -1) '''for''' i = 0<tex>\ldots</tex>n - 1 '''if''' '''not''' marked[0][i] component[i] = 0 '''int''' componentsCount = 0 '''for''' i = 1<tex>\ldots</tex>n - 1 '''if''' '''not''' reachable[i] ''continue'' '''if''' component[i] == -1 componentsCount++ component[i] = componentsCount '''for''' j = i + 1<tex>\ldots</tex>n - 1 '''if''' '''not''' marked[i][j] component[j] = componentsCount <font color="green">// Шаг 6</font> buildDFA(component) <font color="green">// Строим требуемый автомат.</font> ==Асимптотика==Поиск недостижимых состояний с помощью [[Обход_в_глубину,_цвета_вершин | обхода в глубину]] требует <tex>\mathcal{O}(n \cdot |\Sigma|)</tex> времени. Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>\mathcal{O}(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>\mathcal{O}(n^2)</tex>. ==Пример работы==Минимизируем данный автомат: [[Файл:dka.png]] === Шаг <tex>1</tex> ===Строим <tex>\delta^{-1}</tex>. Например, <tex>\delta^{-1}(F, 1) = \{C, D, G, F\}</tex>. === Шаг <tex> 2 </tex> ===Построили массив достижимости состояний из стартового.{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;" !'''Ø'''! A! B! C! D! E! F! G! H|-|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>0</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|} === Шаг <tex> 3 </tex>===Инициализировали таблицу.{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;" !!'''Ø'''! A! B! C! D! E! F! G! H|-!'''Ø'''|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! A|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! B|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! C|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! D|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! E|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! F|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! G|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! H|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||} Вычислили таблицу.{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;" ! !'''Ø'''! A! B! C! D! E! F! G! H|-!'''Ø'''||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! A|align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! B|align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! C|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! D|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! E|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● ||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! F|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! G|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! H|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● ||}
==Время работы алгоритма==Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы Шаг <tex>O(n^2)5 </tex>. Разбиение на ===Из таблицы видно, что классы эквивалентности делается за один проход по таблице, то есть за эквивалентных состояний это <tex>O(n^2) \{A, B\}, \{C, D\}, \{F, G\}, \{E\}, \{H\}</tex>.
==Пример==Минимизируем данный автомат. <br />[[Файл:dka.jpg]]<br />Будем рассматривать только нижний треугольник таблицы пар различимых состояний. <br />Отметили состояния, различающиеся строкой Шаг <tex>\varepsilon6 </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 |}Итого получили такой автомат:
[[Файл:dkaMin.png]]
