Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Абстрактный конечный автомат
Абстрактный конечный автомат – это математическая модель автомата, задаваемая множеством из семи элементов: , где –множество внутренних состояний (алфавит состояний), – начальное состояние конечного автомата, – множество входных сигналов (входной алфавит), – множество выходных сигналов 1-го рода (выходной алфавит 1-го рода), – множество выходных сигналов 2-го рода (выходной алфавит 2-го рода), – функция переходов. Функция переходов показывает, в какое состояние переключится автомат в следующий момент времени, если в данный момент времени автомат находился в состоянии , а на вход поступал сигнал : .
– функция выходов 1-го рода, которая показывает, какой выходной сигнал 1-го рода сформируется на выходе 1-го рода в данный момент времени, если в данный момент времени автомат находился в состоянии a(t), а на вход поступал сигнал z(t): . – функция выходов 2-го рода показывает, какой выходной сигнал 2-го рода сформируется на выходе 2-го рода в данный момент времени, если в данный момент времени автомат находился в состоянии , а на вход поступал сигнал : .
В общем случае абстрактный автомат имеет 1 входной и 2 выходных канала. Такой автомат называют С-автоматом.
В каждый момент времени автомат находится в определенном состоянии . При - в начальном состоянии . Автомат, находящийся в состоянии воспринимает входной сигнал , выдает на выход 1-го рода сигнал , выдает на выход 2-го рода сигнал и переходит в следующий момент времени в состояние . .
Типы конечных автоматов.
Кроме рассмотренного выше С-автомата на практике получили распространение автоматы Мили и автоматы Мура. Автомат Мили
Выходные сигналы автомата Мили - сигналы первого рода. Память автомата характеризуется множеством внутренних состояний автомата. Указывается (обязательно) состояние с которого автомат начинает работу - начальное состояние. Алгоритм работы задается функцией переходов и функцией выходов первого рода: .
Автомат Мура
Выходные сигналы автомата Мура - сигналы второго рода. Алгоритм работы задается функцией переходов и функцией выходов второго рода:
|