Понятие абстрактного автомата

Тема 5.1. Переработка информации с помощью конечных автоматов

Резюме по теме

Вопросы для повторения

1.Маршрут это?

2.В каком случае маршрут называется циклическим?

3.Что представляет собой цепь?

4.В каком случае цепь является простой цепью?

5.Дайте определение Эйлерова цикла?

6.В чем заключается отличие Эйлерова и Гамильтонова циклов?

7.Когда граф называется деревом?

8.Чем являются связные компоненты леса?

9.Вершина называется концевой если?

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

Глава 5. Основы теории конечных автоматов

Цель: рассмотреть основы теории конечных автоматов.

Задачи:

1. Рассмотреть понятие абстрактного автомата.

2. Выявить способы задания автоматов.

3. Рассмотреть взаимосвязь между автоматами Миля и Мура.

Автомат - дискретный преобразователь информации, способный под действием входных сигналов переходить из состояния в состояние и вырабатывать выходные сигналы.

Абстрактный автомат задается с помощью следующей пятерки множеств:

А = { X, Y, S, d, l},

где Х = {X₁, X₂... X_M} – входной алфавит автомата или множество входных символов;

Y = {Y₁, Y₂... Y_N} – выходной алфавит автомата или множество выходных символов;

S = {S₀, S₁... S_K-1} – алфавит или множество внутренних состояний автомата;

S₀ – начальное состояние автомата (в момент времени t = 0).

d – функция переходов;

l - функция выходов автомата.

Автомат называется конечным автоматом, если множества X, Y, S конечны (или счетны).

Автомат функционирует в дискретные моменты времени t = 0, 1, 2...n (рис. 5.1).

Рис. 5.1. Конечный автомат

В каждый момент времени автомат находится в одном из состояний из множества S.

Функция переходов d определяет в каждый момент времени t следующее состояние автомата в зависимости от текущего состояния и входного сигнала или символа входного алфавита. Другими словами, функция d каждой паре «состояние – входной сигнал» ставит в соответствие следующее состояние.

d: S´X ® S; d - есть отображение декартова произведения S´X в S.

Функция переходов может быть записана следующим образом: S_t+1 = d(S_t, X_t ).

Функция выходов l определяет в каждый момент времени t выходной сигнал автомата.

Существует две модели автоматов – автомат Мили и автомат Мура. Они отличаются функцией выходов, которая определяется следующим образом:

Y_t = l (S_t, X_t) - для автомата Мили, или l: S´X®Y.

Y_t = l (S_t) - для автомата Мура.

В автомате Мили выходной сигнал в момент времени t зависит как от входного сигнала в момент времени t, так и от текущего состояния.

В автомате Мура выходной сигнал явно от входного не зависит и определяется только текущим состоянием.

Состояние автомата – это память автомата о прошлых входных воздействиях.

Автоматы также называют последовательностными машинами (Sequential Machines), так как входная последовательность преобразуется в последовательность состояний и выходную последовательность.

Можно сказать, что абстрактный автомат имеет 1 вход и 1 выход. На вход автомата поступают последовательности букв входного алфавита, на выходе формируются выходные последовательности.

Слово или цепочка – это конечная последовательность символов (букв) входного алфавита. Должны выполняться следующие условия (условия автоматности):

1. Длины входных и выходных слов одинаковы;

2. Одинаковым начальным отрезкам входных слов соответствуют одинаковые начальные отрезки выходных слов.

Дата добавления: 2014-01-05