Введение.

Раздел 6

Теория конечных автоматов

 

 

Введение.

 

Теория конечных автоматов исследует тематические модели, приближенно отражающие физические или абстрактные явления, причем эти модели могут быть из области психологии, административного управления, связи, лингвистики, теории ЭВМ и т.д. С помощью конечных автоматов можно исследовать нервную систему животных или человека и проектировать ЭВМ.

Универсальная ЭВМ состоит из 5 устройств:

1) устройство ввода;

2) устройство памяти;

3) арифметическое устройство;

4) устройство управления;

5) устройство вывода.

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

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

Последовательность действий машины определяется программой, которая выполняется последовательно. Сама программа может предусматривать пропуск или повторение информации, хранящейся в памяти, т.е. от внутреннего состояния машины.

ЭВМ бывают цифровые и аналоговые. Мы здесь рассматриваем цифровые. Все сигналы в такой машине двузначны, т. е. принимают значения из множества . Материальные носители и преобразования сигналов – конечны. Множество состояний любой машины также конечно.