Размещено на http://www.allbest.ru/

Федеральное агентство морского и речного транспорта

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Государственный университет морского и речного флота имени адмирала С.О. Макарова»

Кафедра Вычислительных систем и информатики

Курсовая работа

По дисциплине «Языки программирования»

На тему: « Моделирование работы конечного распознавателя»

Вариант № 10

Выполнил:

студент группы ВЗО-ИТ-4

Суворова М.И.

Проверила:

к.т.н. проф.

Крупенина Н.В.

Санкт-Петербург 2014

Содержание

Задание на курсовую работу

Введение

1. Составление формальной грамматики

2. Построение конечного автомата

3. Программное моделирование работы конечного распознавателя

4. Граф детерминированного автомата

5. Блок-схема

6. Примеры разбора строк

Список используемой литературы

Задание на курсовую работу

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

В данной курсовой работе требуется построить детерминированный конечный распознаватель для последовательности составных имен объектов, разделенных слешами, и заканчивающейся символом #, т.е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w/e.w1/re.r5.а#).

Введение

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

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

M = (V, Q, q0, F, в),

где

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

· Q -- множество состояний;

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

· F -- множество заключительных состояний ;

· в -- функция переходов, определенная как отображение

,

такое, что

,

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

Конечный автомат начинает работу в состоянии q0, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x.

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

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

Теоретическая справка.

Недетерминированный конечный автомат (НКА) - это пятерка

M = (Q, T, D, q0, F),

где

· Q - конечное множество состояний;

· T - конечное множество допустимых входных символов (входной алфавит);

· D - функция переходов (отображающая множество QЧ(T{e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;

· q0 Q - начальное состояние управляющего устройства;

· F Q - множество заключительных состояний.

Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 1).

Рис. 1

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

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

Конечный автомат - это модель устройства с конечным числом состояний, которое отличает правильно образованные, или «допустимые» цепочки, от «недопустимых».

1. Составление формальной грамматики

Фраза языка представляет собой список, поэтому из начального символа грамматики должен выводиться список:

R0: <предложение> ::==< фраза>#

R1: <фраза> ::==< фраза>/< составное имя> | <идентификатор>

R2: <составное имя> ::==<составное имя>.<идентификатор>|<идентификатор>

R3: <идентификатор>::==<идентификатор><допустимый символ>|<начальный символ>

R4: <начальный символ>::==<буква>|<знак подчёркивания>

R5: <допустимый символ> :=:=<буква>|<цифра>|<знак подчёркивания>

R6:<буква>::==a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|

R7: <цифра>::==0|1|2|3|4|5|6|7|8|9|

R8:<знак подчёркивания>::==_

Таким образом, требуемую грамматику можно описать следующей структурой:

· Множество терминальных символов: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,I,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,_, .,/,#

· Множество нетерминальных символов: <фраза>, < составное имя>, <идентификатор>, <допустимый символ>, <начальный символ>, <буква>, <цифра>, <знак подчёркивания>.

· Множество правил вывода R0,R1, R2, R3, R4, R5, R6, R7, R8.

2. Построение конечного автомата

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

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

Таблица 1

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z	_	.	/	#
Да	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Нет	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Составное имя	1	1	1	1	1	1	1	1	1	1	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	1	1	1
Идентификатор	5	5	5	5	5	5	5	5	5	5	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	5	2	1
Начальный символ	7	7	7	7	7	7	7	7	7	7	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	8	5	2	1
Допустимый символ	7	7	7	7	7	7	7	7	7	7	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	8	5	1	0
Буква	7	7	7	7	7	7	7	7	7	7	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	8	5	2	0
Цифра	7	7	7	7	7	7	7	7	7	7	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	8	5	2	0
Знак подчёркивания	7	7	7	7	7	7	7	7	7	7	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	8	5	2	0

3. Программное моделирование работы конечного распознавателя

#include <iostream>

#include <string>

#include <iterator>

#include <string.h>

static const char alphabet[] = "0123456789abcdefghijklmnopqrstuvwxyz_./#";

static const size_t alphabetLength = strlen(alphabet);

static const int table[9][alphabetLength]= {

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//Да

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//Нет

{1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,1,1,1},//Составное имя

{7,7,7,7,7,7,7,7,7,7,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,2,1},//Идентификатор

{7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,1},//Начальный символ

{7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,1,0},//Дополнительный символ

{7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0},//Буква

{7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0},//Цифра

{7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0} //Знак

};

int main()

{

std::string input;

std::cin >> input;

std::string::const_iterator it = input.begin();

int state = 2;

while (it != input.end()) {

int alphabetIdex = -1;

for (size_t i=0; i<alphabetLength; ++i) {

if (*it != alphabet[i])

continue;

alphabetIdex = i;

break;

}

state = (alphabetIdex == -1) ? 1 : table[state][alphabetIdex];

it++;

}

if (state == 0) {

std::cout << "STRING is RIGHT" << std::endl;

} else {

std::cout<< "STRING is WRONG" << std::endl;

}

return 0;

}

4. Граф детерминированного автомата

5. Блок-схема

моделирование работа конечный распознаватель

Рисунок 1

6. Примеры разбора строк

Пример входных данных:

q.ad.w/e.w1/re.r5.а#

Пример выходных данных:

STRING is RIGHT

Результат выполнения программы:

Правильный вариант

Рисунок 2

Не правильный вариант

Рисунок 3

Список используемой литературы

1. Крупенина Н.В., Конспект лекций.

2. Щупан, Павловская Структурное программирование.

3. Лаптев Объектно-ориентированное программирование.

4. Опалова Языки программирования и методы трансляции.

Размещено на Allbest.ru

...