Конечный автомат и его программная реализация

Распознаватели регулярных грамматик строятся на конечных автоматах. Конечный автомат – это математическая модель, свойства и поведение которой полностью определяются пятеркой: M = (Q, S, δ, q ₀, F),

где Q – конечное множество состояний;

S – конечное множество входных символов;

δ(q_i, с_k) – функция переходов (q_i – текущее состояние, с_k – очередной символ);

q ₀ – начальное состояние;

F = { q_j } – подмножество допускающих состояний.

Конечные автоматы – одна из базовых моделей, используемых при проектировании программного и аппаратного обеспечения средств вычислительной техники.

Пример. Автомат «Чет-нечет» описывается следующим образом:

Q = {Чет, Нечет};

S = {0, 1};

δ(Чет, 0) = Чет, δ(Нечет, 0) = Нечет, δ(Чет, 1) = Нечет, δ(Нечет, 1) = Чет;

q ₀ = Чет;

F = {Чет}

Строка «10110» приведет такой автомат в состояние Нечет, т. е. будет отвергнута, а строка «110011» – в состояние Чет, т. е. будет принята.

Для представления функции переходов конечного автомата помимо аналитической формы могут использоваться: таблица (см. таблицу 4), граф переходов состояний (см. рисунок 4) и синтаксическая диаграмма (см. рисунок 5).

Таблица 4 – Функция переходов

Рисунок 4 – Граф переходов Рисунок 5 – Синтаксическая диаграмма

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

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

Таблица 5 – Дополненная таблица конечного автомата

Пусть S – строка на входе автомата;

Ind – номер очередного символа;

q – текущее состояние автомата;

Table – таблица, учитывающая символы завершения и другие символы.

Тогда алгоритм работы автомата можно представить следующим образом.

Ind:= 1

q:= q ₀

Цикл-пока q ¹ «Ошибка» и q ¹ «Конец»

q = Table [ q, S [ Ind ]]

Ind:= Ind +1

Поиск по сайту: