Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ОСНОВЫ ТЕОРИИ АВТОМАТОВ

Предметом теории автоматов является изучение математических моделей преобразователей дискретной информации. В данной теории решаются следующие основные задачи: анализ и синтез автоматов; определение полноты; минимизация и эквивалентные преобразования автоматов [2, 6].

Основные понятия и задачи теории автоматов

Задача анализа. По заданному автомату описать его поведение. Вариант постановки: по неполному описанию автомата установить некоторые его свойства.

Задача синтеза. Построить автомат с наперед заданным поведением (алгоритмом функционирования). Задачу синтеза принято рассматривать двояко: абстрактный синтез как построение математической модели автомата и структурный синтез как разработку функциональной логической схемы автомата.

Задача полноты. Пусть М — некоторое множество автоматов. Определить, обладает ли совокупность автоматов, составляющих подмножество М' а М, свойством полноты. Иными словами, если ко всем автоматам подмножества М' конечное число раз применить операцию суперпозиции, совпадут ли М' и Л/?

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

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

 
<<   СОДЕРЖАНИЕ   >>