Реферат: Лабораторные работы по Теории вычислительных процессов и структур

a

a

b

a

#

b

b

Рис.1. Граф конечного автомата.

Можно дать и второе определение конечного автомата. Конечным автоматом (КА) называется совокупность пяти множеств:

КА={N, T, t, S, F}

где : N-конечное множество состояний автомата, совпадающее с множеством нетерминальных символов грамматики;

T-множество терминальных символов автомата, совпадающее с множеством терминальных символов грамматики;

t-функция переходов, задаваемая таблицей;

S- начальное состояние автомата;

F-конечные состояния автомата.

Ф
ункция переходов может быть представлена различными способами. Основные из них: списком команд КА, диаграммой состояний и матрицей переходов. Команда КА представляет собой следующую запись:

(A _i, a _j)A _k

которая представляет собой переход в автомате из вешины А _i в вершину А _k по дуге, отмеченной a _j. Для КА необходимо составлять список таких команд, причём он должен обязательно содержать переходы в конечную вершину, для нормального завершения работы автомата.

Диаграмма состояний это по сути граф КА. И он содержит полную информацию об КА.

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