Математическая энциклопедия » Что такое «Автоматов Эквивалентность»?

Значение слова, определение и толкование термина

Автоматов Эквивалентность

Avtomatov Ekvivalentnost

отношение эквивалентности на множестве автоматов, возникающее в связи с изучением тех или иных содержательных свойств автоматов. Обычно таким свойством является автоматов поведение, так что два автомата считаются эквивалентными, если они имеют одинаковое поведение. При этом в качестве поведения автомата, как правило, рассматривается система функций, реализуемых автоматом (см. Автомат конечный). Для конечных автоматов такое отношение эквивалентности разрешимо, и потому существует алгоритм минимизации автоматов, т. е. построения для заданного автомата эквивалентного ему автомата с минимальным числом состояний (минимального автомата).

Для определения А. э. удобно использовать понятие эквивалентности состояний: состояния [Автоматов Эквивалентность. Фото 1] соответственно автоматов [Автоматов Эквивалентность. Фото 2] (быть может, совпадающих) наз. эквивалентными, если инициальные автоматы [Автоматов Эквивалентность. Фото 3] реализуют одну и ту же функцию. Тогда эквивалентность автоматов [Автоматов Эквивалентность. Фото 4] равносильна тому, что для любого состояния автомата [Автоматов Эквивалентность. Фото 5] найдется эквивалентное ему состояние автомата [Автоматов Эквивалентность. Фото 6] и обратно. Автомат является минимальным тогда и только тогда, когда любые два его состояния неэквивалентны. Для любого автомата минимальный автомат определяется однозначно с точностью до изоморфизма. Алгоритм разрешения этого отношения эквивалентности для конечных автоматов основывается на теореме Мура о том, что состояния [Автоматов Эквивалентность. Фото 7] автомата [Автоматов Эквивалентность. Фото 8] эквивалентны точно тогда, когда функции, реализуемые инициальными автоматами [Автоматов Эквивалентность. Фото 9] совпадают на словах длины [Автоматов Эквивалентность. Фото 10] где [Автоматов Эквивалентность. Фото 11]- число состояний автомата [Автоматов Эквивалентность. Фото 12] В случае, когда состояния [Автоматов Эквивалентность. Фото 13] принадлежат, соответственно, двум автоматам [Автоматов Эквивалентность. Фото 14] эта оценка равна [Автоматов Эквивалентность. Фото 15] - число состояний автомата [Автоматов Эквивалентность. Фото 16] На этой же теореме основан известный алгоритм минимизации конечных автоматов, состоящий в построении так наз. приведенного автомата, состояниями к-рого являются классы эквивалентных состояний, а функции переходов и выходов естественно индуцируются соответствующими функциями исходного автомата. Приведенный автомат является минимальным, поскольку любые два его состояния неэквивалентны.

Существуют асимптотич. оценки числа [Автоматов Эквивалентность. Фото 17] минимальных автоматов с псостояниями, то входными и рвыходными буквами; при условии, что [Автоматов Эквивалентность. Фото 18] для [Автоматов Эквивалентность. Фото 19] имеет место оценка [Автоматов Эквивалентность. Фото 20] в то время как [Автоматов Эквивалентность. Фото 21] Другой задачей, связанной с изучением А. э., является проблема эквивалентных преобразований автоматов. Эта задача рассматривалась применительно к двум формам задания конечных автоматов - диаграммам и логическим сетям. В общем виде она состоит в том, чтобы найти систему правил преобразований, удовлетворяющих определенным условиям и позволяющих преобразовать произвольный автомат в любой эквивалентный ему автомат,- т. н. полную систему правил. В обоих случаях правило преобразования представляет собой пару схем (фрагментов диаграмм или логич. сетей), реализующих одинаковые наборы отображений. Применение такого правила состоит в замене одного фрагмента другим. Для конечных автоматов полной системы таких правил не существует. Однако для логич. сетей с ограниченным числом задержек такая система существует.

Основные понятия, проблематика и методы, возникающие при изучении эквивалентности конечных автоматов, как правило, переносятся и на другие типы автоматов с учетом их особенностей.

Лит. СМ; при статье Автомат.

В. Б. Кудрявцев, Ю. И. Янов.

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также