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

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

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

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

Н. Полную систему правил. В обоих случаях правило преобразования представляет собой пару схем (фрагментов диаграмм или логич. Сетей), реализующих одинаковые наборы отображений. Применение такого правила состоит в замене одного фрагмента другим. Для конечных автоматов полной системы таких правил не существует. Однако для логич. Сетей с ограниченным числом задержек такая система существует. Основные понятия, проблематика и методы, возникающие при изучении эквивалентности конечных автоматов, как правило, переносятся и на другие типы автоматов с учетом их особенностей. Лит. СМ. При статье Автомат. В. Б. Кудрявцев, Ю. И. Янов.