Разработка конечного автомата

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 8Следующая ⇒

Цель работы - приобретение практических навыков разработки и проектирования конечных автоматов.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Краткое теоретическое введение

С помощью конечного автомата, представленного в виде графа, можно реализовать любую регулярную грамматику

G = (N,T,P,S),

где

N - множество нетерминальных символов;

T - множество терминальных символов;

P - множество правил (продукций) грамматики;

S - начальное состояние грамматики (начальный нетерминальный символ).

Конечный автомат - это пятерка объектов (K,VT,M,S,Z), где

К - алфавит элементов, называемых состояниями;

VT - алфавит, называемый входным алфавитом (символы, которые могут встретиться в цепочке);

М - отображение (или функция) множества КхVT во множество К (если М(Q,T) = R, то это означает, что из состояния Q при входном символе Т происходит переключение в состояние R);

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

Z - непустое множество заключительных состояний из множества К.

Вывод цепочки языка в грамматике интерпретируется на графе как путь от начальной вершины к одной из заключительных, причем для получения самой цепочки нужно выписать все символы, помечающие пройденные дуги в порядке их прохождения.

Если в процессе вывода цепочки языка для текущего символа нет дуг, помеченных данным символом, то это означает, что цепочка не входит в язык, и процедура закончена.

Если по исчерпании символов цепочки оказывается, что достигнута конечная вершина, то процедура закончена и цепочка входит в язык.

Пример

Рассмотрим регулярную грамматику G = (N,T,P,S)

S::= A0|B1

A::= S1|1

B::= S0|0

Порождаемый данной грамматикой язык состоит из последовательностей, образуемых парами 01 или 10, т.е.

, где B = {01, 10}.

Данной грамматике G соответствует конечный автомат с состояниями S,A,B,Z, где

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

Z - конечное состояние.

Граф для конечного автомата представлен на рис. 1.1.

Рис. 1.1

Матрица переходов состояний для данного конечного автомата представлена в табл. 1.1.

Таблица 1.1

Например, цепочка "10010110" входит в язык, а цепочка "110110" - нет.

ЗАДАНИЕ

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

Примечание.

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

СОДЕРЖАНИЕ ОТЧЕТА

Отчет о выполнении лабораторной работы должен содержать:

· титульный лист;

· задание;

· граф для конечного автомата;

· укрупненную схему программы;

· листинг программы;

· результаты тестирования;

· выводы по выполненной работе.

ВАРИАНТЫ ЗАДАНИЙ

Варианты заданий представлены в табл. 1.2.

Таблица 1.2

ЛАБОРАТОРНАЯ РАБОТА № 2

Разработка детерминированного конечного автомата
по регулярному выражению и недетерминированному
конечному автомату

Цель работы - приобретение практических навыков детерминирования конечных автоматов.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии