АВТОМАТОВ ЭКВИВАЛЕНТНОСТЬ

АВТОМАТОВ ЭКВИВАЛЕНТНОСТЬ

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

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

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

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

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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "АВТОМАТОВ ЭКВИВАЛЕНТНОСТЬ" в других словарях:

  • АВТОМАТОВ ГОМОМОРФИЗМ — отображение входного и выходного алфавитов, а также множества состояний одного автомата в аналогичные множества другого автомата, сохраняющее функции переходов и выходов. Более точно А. г. автомата в автомат (см. Автомат конечный) это отображение …   Математическая энциклопедия

  • Автоматов теория —         часть теоретической кибернетики (См. Кибернетика), объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50 х гг. 20 в. в связи с требованиями практики проектирования вычислительных… …   Большая советская энциклопедия

  • Эквивалентность детерминированных и недетерминированных конечных автоматов — Конечный автомат  в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно.… …   Википедия

  • АЛГЕБРА ЛОГИКИ —         система алгебраич. методов решения логич. задач, а также совокупность задач, решаемых такими методами. А. л. в узком смысле слова алгебраич. (табличное, матричное) построение классич. логики высказываний, в котором рассматриваются… …   Философская энциклопедия

  • ПОЛИГОН — над моноидом R, R полигон, операнд, непустое множество с моноидом операторов. Точнее, непустое множество Аназ. левым П. над моноидом К, если для любых и определено произведение , причем и 1а=а для любых . Правый П. определяется аналогично.… …   Математическая энциклопедия

  • Построение синтаксического анализатора на основе автоматного подхода — Построение синтаксического анализатора на основе автоматного подхода  один из способов построения синтаксического анализатора, использующий представление анализируемого языка в виде конечного автомата. Содержание 1 Алгоритм синтаксического… …   Википедия

  • Теорема Клини — Главный тезис Теоремы Клини: «Классы регулярных множеств и автоматных языков совпадают». Доказательство теоремы Клини Любой граф переходов конечного автомата всегда можно представить в нормализованной форме, в которой только одна начальная… …   Википедия

  • КОМБИНАТОРНЫЙ АНАЛИЗ — комбинаторная математика, комбинаторика, раздел математики, посвященный решению задач выбора и расположения элементов нек рого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения… …   Математическая энциклопедия

  • Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер …   Википедия

  • ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ — управ ляющих систем преобразования, сохраняющие отношение эквивалентности (о. э.) управляющих систем (у. с.). Используются в задачах оптимизации, контроля, а также как средство характеризации (напр., аксиоматизации) определенных классов у. с.;… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»