Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Определение конечного автомата

Читайте также:
  1. I. Определение группы.
  2. I. ОПРЕДЕЛЕНИЕ И ПРОБЛЕМЫ МЕТОДА
  3. I. Определение и проблемы метода
  4. III. Определение средней температуры подвода и отвода теплоты
  5. IX. Империализм и право наций на самоопределение
  6. А) Определение, предназначение и история формирования государственного резерва.
  7. А) философское определение материи

Лекция № 16

ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ

Понятие конечного автомата

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

По входному каналу в каждый данный момент времени t = 1, 2, … в устройство М поступают входные (из некоторые конечного множества сигналов). Задается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал зависит от состояния и входного сигнала в текущий момент времени.

Определение конечного автомата

Конечный автомат является математической моделью реальных дискретных устройств по переработке информации.

Конечным автоматом называется система A = (X, Q, Y, φ, ψ), где X, Q, Y – произвольные не пустые конечные множества.

Множество X = {x1, x2,, xm} называется входным алфавитом, а его элементы – входными сигналами, а их последовательности - входными словами.

Множество Q = {q1, q2,, qn} называется множеством состояний, автомата, а его элементы – состояниями.

Множество Y = {y1, y2,, yp} называется вsходным алфавитом, а его элементы – выходными сигналами, а их последовательности - выходными словами.

Функции φ: XЧQ → Q называется функцией переходов. Функции ψ: XЧQ → Y называется функцией выходов т.е. φ(x, q) Q; ψ(x, q) Y для x X; q Q.

С конечным автоматом ассоциируется воображаемое устройство, которое работает следующим образом. Конкретное устройство может находиться либо в состоянии на множестве Q, либо воспринимать сигналы из множества X и наконец выдавать сигналы из множества Y.

 


Дата добавления: 2015-07-07; просмотров: 167 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Рецидив| ВОПРОС 1. Охлаждение до низких положительных температур.

mybiblioteka.su - 2015-2024 год. (0.009 сек.)