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

 

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

 

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

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

 

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

 

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

 

Состояния	Входной алфавит
S	B	A
A	Z	---
B	---	Z
Z	B	A

 

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

 

ЗАДАНИЕ

 

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

 

Примечание.

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

 

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

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

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

· задание;

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

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

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

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

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

 

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

 

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

 

Таблица 1.2

 

№ варианта	Состояния	Входной алфавит
1.	S	B	A	---	---
A	---	---	A	Z
B	---	Z	---	B
Z	B	---	A	---
2.	S	C	B	A
A	---	Z	A
B	Z	B	---
C	C	---	Z
Z	A	C	B
3.	S	B	---	A	---
A	---	A	---	Z
B	Z	---	B	---
Z	---	A	---	B
4.	S	A	C	B
A	Z	A	---
B	B	Z	---
C	Z	---	C
Z	C	A	B
5.	S	A	---	B	---
A	A	---	Z	---
B	---	B	---	Z
Z	A	B	---	---
6.	S	A	B	C
A	A	---	Z
B	Z	---	B
C	---	C	Z
Z	C	B	A
7.	S	A	B	---	---
A	---	A	---	Z
B	Z	---	B	---
Z	A	---	B	---
8.	S	B	C	A
A	Z	---	A
B	B	Z	---
C	Z	---	C
Z	A	C	B
9.	S	B	A	---	---
A	A	---	Z	---
B	B	---	Z	---
Z	---	---	B	A
10.	S	A	B	C
A	A	Z	---
B	---	B	Z
C	Z	---	C
Z	C	B	A
11.	S	B	---	A	---
A	---	A	---	Z
B	B	---	---	Z
Z	---	B	A	---
12.	S	C	B	A
A	Z	A	---
B	Z	---	B
C	Z	C	---
Z	A	B	C

 

 

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

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

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

 

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