О минимизации автоматов алгоритмом Хопкрофта
Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в эт...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/113327 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862529141898739712 |
|---|---|
| author | Чеботарев, А.Н. |
| author_facet | Чеботарев, А.Н. |
| citation_txt | О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве.
Розглянуто алгоритм Хопкрофта для мінімізації детермінованих всюди визначених скінченних автоматів. Дано зрозуміле до ведення коректності алгоритму та оцінки часової складності. Доведення базується на запропонованому понятті дерева розщеплень і методі розповсюдження «закритих» вузлів у цьому дереві.
The algorithm for minimizing deterministic complete finite state automata proposed by J. Hopcroft is considered. Although the existence of this algorithm is widely known, its theoretical justification is not that obvious. The aim of this study is to give a clear and understandable presentation of the algorithm focusing on the firm theoretical basis, rigorous correctness proof and time complexity analysis. The algorithm is based on the partition notion of the automaton states which defines the equivalence relation. It constructs a sequence of such partitions by a stepwise refinement of some initial partition. The last partition in this sequence corresponds to the maximal congruence on the automaton’s states, i.e., the equivalence stable with respect to the transition function of the automaton. To prove correctness of the algorithm it is necessary to show that the final constructed partition is a congruence, and that this congruence is maximal. In the first part of this proof, the introduced notion of binary splitting tree is used whose nodes are classes of the partitions constructing by the algorithm and a technique for extending the so called “closed” nodes of this tree. The second part is based on the proposition concerning the order on partitions. It is proved that every partition in the sequence generated by the algorithm is greater than or equal to the partition corresponding to the maximal congruence. It is show that Hopcroft’s algorithm can be implemented to worst-case time complexity O (kn log n) for an automaton with n states over a k-letter alphabet. This statement relies on the fact that the total number of actions refining the partitions over all steps of algorithm execution is of the order of O(kn log n). The data structures which allow obtaining this time complexity is presented. The last section describes the algorithm features for minimizing Moore and Mealy automata.
|
| first_indexed | 2025-11-24T02:20:30Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-113327 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-11-24T02:20:30Z |
| publishDate | 2016 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Чеботарев, А.Н. 2017-02-06T15:25:38Z 2017-02-06T15:25:38Z 2016 О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113327 519.713 Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве. Розглянуто алгоритм Хопкрофта для мінімізації детермінованих всюди визначених скінченних автоматів. Дано зрозуміле до ведення коректності алгоритму та оцінки часової складності. Доведення базується на запропонованому понятті дерева розщеплень і методі розповсюдження «закритих» вузлів у цьому дереві. The algorithm for minimizing deterministic complete finite state automata proposed by J. Hopcroft is considered. Although the existence of this algorithm is widely known, its theoretical justification is not that obvious. The aim of this study is to give a clear and understandable presentation of the algorithm focusing on the firm theoretical basis, rigorous correctness proof and time complexity analysis. The algorithm is based on the partition notion of the automaton states which defines the equivalence relation. It constructs a sequence of such partitions by a stepwise refinement of some initial partition. The last partition in this sequence corresponds to the maximal congruence on the automaton’s states, i.e., the equivalence stable with respect to the transition function of the automaton. To prove correctness of the algorithm it is necessary to show that the final constructed partition is a congruence, and that this congruence is maximal. In the first part of this proof, the introduced notion of binary splitting tree is used whose nodes are classes of the partitions constructing by the algorithm and a technique for extending the so called “closed” nodes of this tree. The second part is based on the proposition concerning the order on partitions. It is proved that every partition in the sequence generated by the algorithm is greater than or equal to the partition corresponding to the maximal congruence. It is show that Hopcroft’s algorithm can be implemented to worst-case time complexity O (kn log n) for an automaton with n states over a k-letter alphabet. This statement relies on the fact that the total number of actions refining the partitions over all steps of algorithm execution is of the order of O(kn log n). The data structures which allow obtaining this time complexity is presented. The last section describes the algorithm features for minimizing Moore and Mealy automata. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Программная инженерия и программные средства О минимизации автоматов алгоритмом Хопкрофта Про мінімізацію автоматів алгоритмом Хопкрофта On Automata Minimization by Hopcroft’s Algorithm Article published earlier |
| spellingShingle | О минимизации автоматов алгоритмом Хопкрофта Чеботарев, А.Н. Программная инженерия и программные средства |
| title | О минимизации автоматов алгоритмом Хопкрофта |
| title_alt | Про мінімізацію автоматів алгоритмом Хопкрофта On Automata Minimization by Hopcroft’s Algorithm |
| title_full | О минимизации автоматов алгоритмом Хопкрофта |
| title_fullStr | О минимизации автоматов алгоритмом Хопкрофта |
| title_full_unstemmed | О минимизации автоматов алгоритмом Хопкрофта |
| title_short | О минимизации автоматов алгоритмом Хопкрофта |
| title_sort | о минимизации автоматов алгоритмом хопкрофта |
| topic | Программная инженерия и программные средства |
| topic_facet | Программная инженерия и программные средства |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113327 |
| work_keys_str_mv | AT čebotarevan ominimizaciiavtomatovalgoritmomhopkrofta AT čebotarevan promínímízacíûavtomatívalgoritmomhopkrofta AT čebotarevan onautomataminimizationbyhopcroftsalgorithm |