==Определения==
{{Определение
|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> '''эквивалентны''', если они не различимы никакой строкой.
}}
{{Теорема
|statement =
Введённое выше отношение является [[Транзитивное отношение#Отношение эквивалентности. Класс эквивалентности|отношением эквивалентности]].
|proof =
<ol>
<li> <tex>u \thicksim u</tex> — очевидно. </li>
<li> <tex>u\thicksim v \Rightarrow v\thicksim u</tex> — очевидно. </li>
<li> <tex>u\thicksim v, v\thicksim z \Rightarrow u\thicksim z</tex>. Пусть <tex>u</tex> и <tex>z</tex> неэквивалентны. Тогда <tex> \mathcal {9} s</tex> такая, что
<ol>
<li><tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>, </li>
<li><tex> \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle </tex>, где <tex>t_1 \notin T </tex>. </li>
</ol>
Рассмотрим <tex>x</tex> такой, что <tex> \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle </tex>. <br />
Если <tex>x \in T</tex>, то <tex>v</tex> и <tex>z</tex> различимы строкой <tex>s</tex>. Противоречие. <br />
Если <tex>x \notin T</tex>, то <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex>. Противоречие. <br />
Значит, <tex>u</tex> и <tex>z</tex> эквивалентны.</li>
</ol>
}}
==Постановка задачи==
Пусть дан автомат <tex>A</tex>. Требуется построить автомат <tex>A_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>A</tex>.
==Алгоритм==
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности ]] — они и будут состояниями минимизированного автомата. <br />
Для реализации алгоритма нам потребуются очередь <tex>Q</tex> и таблица размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. <br />
Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний ]] и класть их в очередь. <br />
Изначально добавим в очередь <tex>Q</tex> пары состояний, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.
Пока <tex>Q</tex> не станет пуста, будем делать следующее:
