• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

О проблеме эквивалентности недетерминированных автоматов-преобразователей над однобуквенным выходным алфавитом

Захаров В. А., Жайлауова Ш. Р.

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