САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТ ВОДНЫХ КОММУНИКАЦИЙ
Кафедра ВСиИ
КУРСОВАЯ РАБОТА
по дисциплине «Системное программноеобеспечение»
Моделирование работы конечногораспознавателя для последовательности элементов типа «дата» в немецком формате,разделенных запятыми и заключённых в фигурные скобки
Вариант № 15
Выполнил:
студент группы ИС-31
Мельников А.
Санкт-Петербург
2009 год
Содержание
Задание на курсовую работу
Введение
1 Составление формальной грамматики
2 Построение конечного автомата
3 Программное моделированиеработы конечного автомата
4 Граф детерминированногоавтомата
5 Блок-схема
6 Примеры разбора строк
Задание на курсовуюработу
Моделирование работыконечного распознавателя для последовательности элементов типа «дата» в немецком формате(ДД.ММ.ГГГГ), разделенных запятыми, при этом значение даты должно быть помещенов фигурные скобки, а год должен отображаться четырьмя символами, например,({01.12.2001},{05.07.2003});
Введение
Учебная цель. Получение практических навыковпостроения моделей конечных распознавателей.
Теоретические сведения.
Недетерминированныйконечный автомат (НКА) — это пятерка M = (Q, T, D, q0, F), где
· Q — конечноемножество состояний;
· T — конечноемножество допустимых входных символов (входной алфавит);
· D — функцияпереходов (отображающая множество Q(T/>{e}) во множество подмножествмножества Q), определяющая поведение управляющего устройства;
· q0/>Q — начальноесостояние управляющего устройства;
· F />Q — множествозаключительных состояний.
Недетерминизмавтомата заключается в том, что, во-первых, находясь в некотором состоянии иобозревая текущий символ, автомат может перейти в одно из, вообще говоря,нескольких возможных состояний, и во-вторых, автомат может делать переходы поe.
Пусть M = (Q,T, D, q0, F) — НКА. Конфигурацией автомата M называется пара (q, w) />QT*,где q — текущее состояние управляющего устройства, а w — цепочка символов навходной ленте, состоящая из символа под головкой и всех символов справа отнего. Конфигурация (q0, w) называется начальной, а конфигурация (q,e), где q />F- заключительной (или допускающей).
Пусть M = (Q,T, D, q0, F) — НКА. Тактом автомата M называется бинарное отношение />, определенноена конфигурациях M следующим образом: если p />D(q, a), где a />T />{e}, то (q, aw) />(p, w) для всехw />T*.
Будемобозначать символом />+ (/>*)транзитивное (рефлексивно- транзитивное) замыкание отношения />.
Говорят, чтоавтомат M допускает цепочку w, если (q0, w) />*(q, e) для некоторогоq />F.Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначаетсяL(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е.
/>
Важнымчастным случаем недетерминированного конечного автомата являетсядетерминированный конечный автомат, который на каждом такте работы имеетвозможность перейти не более чем в одно состояние и не может делать переходы поe.
Пусть M = (Q,T, D, q0, F) — НКА. Будем называть M детерминированным конечнымавтоматом (ДКА), если выполнены следующие два условия:
· D(q, e) = />для любого q />Q, и
· D(q, a) содержитне более одного элемента для любых q />Q и a />T.
Так какфункция переходов ДКА содержит не более одного элемента для любой парыаргументов, для ДКА мы будем пользоваться записью D(q, a) = p вместо D(q, a) ={p}.
Конечныйавтомат может быть изображен графически в виде диаграммы, представляющей собойориентированный граф, в котором каждому состоянию соответствует вершина, адуга, помеченная символом a />T />{e}, соединяет две вершины p и q,если p />D(q,a). На диаграмме выделяются начальное и заключительные состояния.
Конечныйраспознаватель – этомодель устройства с конечным числом состояний, которое отличает правильнообразованные, или «допустимые» цепочки, от «недопустимых».
Примером задачираспознавания может служить проверка нечетности числа единиц в произвольнойцепочке, состоящей из нулей и единиц. Соответствующий конечный автомат будетдопускать все цепочки, содержащие нечетное число единиц, и отвергать всецепочки с четным их числом. Назовем его «контролером нечетности».
На вход конечногоавтомата подается цепочка символов из конечного множества, называемого входнымалфавитом автомата, и представляющего собой совокупность символов, дляработы с которыми он предназначен. Как допускаемые, так и отвергаемые автоматомцепочки, состоят только из символов входного алфавита. Символы, непринадлежащие входному алфавиту, нельзя подавать на вход автомата. Входнойалфавит контроллера нечетности состоит из двух символов: «0» и «1».
В каждый момент времениконечный автомат имеет дело лишь с одним входным символом, а информацию опредыдущих символах входной цепочки сохраняет с помощью конечного множествасостояний. Согласно этому представлению, автомат помнит о прочитанных ранеесимволах только то, что при их обработке он перешел в некоторое состояние, котороеи является памятью автомата о прошлом.
Работу автомата можноописать математически с помощью функции переходов, которая по текущемусостоянию /> и текущему входному символу/> дает новое состояниеавтомата />. Символически этазависимость описывается так:
/>.
Некоторые состоянияавтомата выбираются в качестве допускающих, или заключительных.Если автомат, начав работу в начальном состоянии, при прочтении всей цепочкипереходит в одно из допускающих состояний, то говорят, что эта цепочкадопускается автоматом. Если последнее состояние автомата не является допускающим,то говорят, что автомат отвергает цепочку.
1 Составлениеформальной грамматики
Фраза языка представляет собойсписок, поэтому из начального символа грамматики должен выводится список:
R0:::==
R1: ::== |,
Дата представляет собойлинейную структуру:
R2:::=={.}
Аналогично год, месяц идень:
R3:::==
R4: : :== . |. |
R5: ::=01|03|05|07|08|10|12
R6: ::=04|06|09|11
R7: ::=02
R8:::==| 3
R9:::==| 30
R10:::==| 2
R11:::==0|1|2|3|4|5|6|7|8|9|
R12: ::==0|1
R13: ::==0|1|2
R14:::==0|1|2|3|4|5|6|7|8
Таким образом, требуемуюграмматику можно описать следующей структурой:
· Множествотерминальных символов: {, }, .,, ,0,1,2,3,4,5,6,7,8,9.
· Множествонетерминальных символов: , , ,, , , , .
· Множество правилвывода R0,R1, R2, R3, R4, R5, R6, R7, R8, R9, R10, R11, R12, R13, R14.
2 Построение конечногоавтомата
Между конечными автоматами иавтоматными грамматиками существует тесная связь: класс языков, допускаемых конечнымиавтоматами, совпадает с классом языков, порождаемых автоматными грамматиками.
Для построения конечногоавтомата составленную грамматику путем введения дополнительных состояний надопреобразовать к автоматному виду, в результате получится следующая таблицапереходов: 1 2 3 4 5 6 7 8 9 { } . , да нет день нет нет нет нет нет нет нет нет нет нет нет нет денф нет денб Дб1 Дб1 Дб1 Цф1 нет нет нет нет нет нет нет нет нет нет Дб1 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 нет нет нет нет Дб2 нет нет нет нет нет нет нет нет нет нет нет нет мес нет Цф1 Дб2 Дб2 нет нет нет нет нет нет нет нет нет нет нет нет денм Дб1 Дб1 Дб1 Цф0 нет нет нет нет нет нет нет нет нет нет Цф0 Дб2 нет нет нет нет нет нет нет нет нет нет нет нет нет денф Дб1 Дб1 Цф3 нет нет нет нет нет нет нет нет нет нет нет Цф3 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 Дб2 нет нет нет нет нет нет мес Мес0 Мес1 нет нет нет нет нет нет нет нет нет нет нет нет Мес0 нет месб фев месб месм месб месм месб месб месм нет нет нет нет Мес1 месб месм месб нет нет нет нет нет нет нет нет нет нет нет месб нет нет нет нет нет нет нет нет нет нет нет нет денб нет месм нет нет нет нет нет нет нет нет нет нет нет нет денм нет дата нет нет нет нет нет нет нет нет нет нет год нет нет нет год Цг1 Цг1 Цг1 Цг1 Цг1 Цг1 Цг1 Цг1 Цг1 Цг1 нет нет нет нет Цг1 Цг2 Цг2 Цг2 Цг2 Цг2 Цг2 Цг2 Цг2 Цг2 Цг2 нет нет нет нет Цг2 Цг3 Цг3 Цг3 Цг3 Цг3 Цг3 Цг3 Цг3 Цг3 Цг3 нет нет нет нет Цг3 Цг4 Цг4 Цг4 Цг4 Цг4 Цг4 Цг4 Цг4 Цг4 Цг4 нет нет нет нет Цг4 нет нет нет нет нет нет нет нет нет нет нет да нет день
3 Графдетерминированного автомата
Для того, чтобы улучшитьзрительное восприятие и облегчить понимание сложных синтаксических описаний,часто применяют представление правил грамматики в виде синтаксических диаграмм.
Синтаксическая диаграммапредставляет собой ориентированный граф для каждого правила грамматики.
4 Программное моделированиеработы конечного автомата
#include«iostream.h»
#include«stdio.h»
#include«conio.h»
int main()
{inti,j,kol,tsost,slsost,tsymb;
inttabl[24][14]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0},//da
{1,1,1,1,1,1,1,1,1,1,1,1,1,1},//net
{1,1,1,1,1,1,1,1,1,1,3,1,1,1},
{4,4,4,5,1,1,1,1,1,1,1,1,1,1},
{1,6,6,6,6,6,6,6,6,6,1,1,1,1},
{8,9,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,20,1},
{16,16,16,16,16,16,16,16,16,16,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,10,1},
{1,1,1,1,1,1,1,1,1,1,1,1,11,1},
{12,13,1,1,1,1,1,1,1,1,1,1,1,1},
{14,15,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,23,1,23,1,1,23,1,1,1,1},
{23,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,23,1,23,1,23,1,23,23,1,1,1,1,1},
{23,1,23,1,1,1,1,1,1,1,1,1,1,1},
{17,17,17,17,17,17,17,17,17,17,1,1,1,1},
{18,18,18,18,18,18,18,18,18,18,1,1,1,1},
{19,19,19,19,19,19,19,19,19,19,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,0,1,2},
{21,22,1,1,1,1,1,1,1,1,1,1,1,1},
{1,23,23,23,23,23,23,23,23,23,1,1,1,1},
{23,23,23,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,7,1},
};
printf(«matrica\n»);
for(i=0;i
char ch,inpstr[80] ;
printf("\n ENTER STRING ");
i=0;
while((ch=getch()) !=13 && i
{putch(ch);
inpstr[i++]=ch;}
inpstr[i]='\0';
kol=i-1;
printf("\ninput string:");
printf(inpstr);
printf("\n");
tsost=2;
for(i=0;i
{ tsymb=inpstr[i];
switch (tsymb)
{ case '0': slsost=tabl[tsost][0]; break;
case '1': slsost=tabl[tsost][1]; break;
case '2': slsost=tabl[tsost][2]; break;
case '3': slsost=tabl[tsost][3]; break;
case '4': slsost=tabl[tsost][4]; break;
case '5': slsost=tabl[tsost][5]; break;
case '6': slsost=tabl[tsost][6]; break;
case '7': slsost=tabl[tsost][7]; break;
case '8': slsost=tabl[tsost][8]; break;
case '9': slsost=tabl[tsost][9]; break;
case '{': slsost=tabl[tsost][10]; break;
case '}': slsost=tabl[tsost][11]; break;
case '.': slsost=tabl[tsost][12];break;
case ',': slsost=tabl[tsost][13]; break;
default:slsost=1;}
printf("%5d\n",slsost);
tsost=slsost;
};
switch(slsost)
{ case1:cout
case0:cout
return 0;
};
5 Блок-схема
/>
6 Примеры
Правильные строки:
/>
/>
Неправильныестроки:
/>
/>