Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


Моделирование работы конечного распознавателя для последовательно-сти элементов типа "дата" в немецком формате, разделенных запятыми и заключённых в фигурные скобки

Тип Реферат
Предмет Информатика и программирование
Просмотров
1214
Размер файла
170 б
Поделиться

Ознакомительный фрагмент работы:

Моделирование работы конечного распознавателя для последовательно-сти элементов типа "дата" в немецком формате, разделенных запятыми и заключённых в фигурные скобки

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ВОДНЫХ КОММУНИКАЦИЙ

Кафедра ВСиИ

КУРСОВАЯ РАБОТА

по дисциплине «Системное программное обеспечение»

Моделирование работы конечного распознавателя для последовательности элементов типа «дата» в немецком формате, разделенных запятыми и заключённых в фигурные скобки

Вариант № 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), определяющая поведение управляющего устройства;

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

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

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

Пусть M = (Q, T, D, q0, F) - НКА. Конфигурацией автомата M называется пара (q, w) QT*, где 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: <деньб>::==<цифра2><цифра>| 3<цифра1>

R9: <деньм>::==<цифра2><цифра>| 30

R10: <деньф>::==<цифра1><цифра>| 2<цифра3>

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

R12: <цифра1>::==0|1

R13: <цифра2>::==0|1|2

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

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

· Множество терминальных символов: {, }, ., , ,0,1,2,3,4,5,6,7,8,9.

· Множество нетерминальных символов: <фраза>, <дата>, <год>, <месяц>, <день>, <цифра>, <цифра1>, <цифра2>.

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

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

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

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

0123456789{}.,
да
нет
деньнетнетнетнетнетнетнетнетнетнетнетнетденфнет
денбДб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()

{int i,j,kol,tsost,slsost,tsymb;

int tabl[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("matrican");

for (i=0;i<24;i++) {for (j=0;j<14;j++) printf("%4d",tabl[i][j]); printf("n");};

char ch, inpstr[80] ;

printf("n ENTER STRING ");

i=0;

while ((ch=getch()) !=13 && i<80)

{putch(ch);

inpstr[i++]=ch;}

inpstr[i]=' ';

kol=i-1;

printf("n input string:");

printf(inpstr);

printf("n");

tsost=2;

for (i=0;i<=kol;i=i+1)

{ 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("%5dn",slsost);

tsost=slsost;

};

switch (slsost)

{ case 1:cout<<"n STRING is WRONG n"; break;

case 0:cout<<"n STRING is RIGHT n";break;}

return 0;

};


5 Блок-схема

6 Примеры

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

Неправильные строки:


Нет нужной работы в каталоге?

Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

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

avatar
Математика
История
Экономика
icon
147595
рейтинг
icon
3128
работ сдано
icon
1351
отзывов
avatar
Математика
Физика
История
icon
142374
рейтинг
icon
5881
работ сдано
icon
2654
отзывов
avatar
Химия
Экономика
Биология
icon
95355
рейтинг
icon
2031
работ сдано
icon
1273
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
54 191 оценка star star star star star
среднее 4.9 из 5
РГРТУ
Благодарю за проделанную работу! Работа выполнена досрочно, без каких либо замечаний
star star star star star
ЛГТУ
Отличный исполнитель. Все время на связи, все просьбы по доработки от преподавателя быстро...
star star star star star
ТГУ
Все сделано досрочно. Претензий при проверке задания не было. Работа выполнена качественно...
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

Здравствуйте, сможете ли продолжить выполнение задания в Archicad на...

Курсовая, Компьтерная графика

Срок сдачи к 19 сент.

только что

Сделать чертеж детали в компасе v21

Чертеж, начертательная геометрия и инженерная графика

Срок сдачи к 18 сент.

только что

Выполнить практическую работу по форме

Лабораторная, Обеспечение качества изделий

Срок сдачи к 18 сент.

2 минуты назад

Выполнить ИДЗ

Другое, Обеспечение качества изделий

Срок сдачи к 18 сент.

3 минуты назад

Изменение операционной системы

Курсовая, Электротехника

Срок сдачи к 25 мая

3 минуты назад

Выполнить практическую работу по форме

Лабораторная, Обеспечение качества изделий

Срок сдачи к 18 сент.

4 минуты назад

Расчет показателей макроэкономики

Решение задач, Отраслевая структура национальной экономики

Срок сдачи к 19 сент.

4 минуты назад

Тема на выбор

Курсовая, Экономика

Срок сдачи к 27 сент.

5 минут назад

Две задачи решить

Решение задач, Акушерство

Срок сдачи к 6 окт.

5 минут назад

пробник - индикатор низкочастотных сигналов

Курсовая, разработка и проектирование цифровых устройств

Срок сдачи к 24 сент.

5 минут назад

Решить контрольную 5 и 6

Контрольная, Высшая математика

Срок сдачи к 18 сент.

6 минут назад

Особенности агрессивных проявлений у подростков

Курсовая, Психология и педагогика

Срок сдачи к 27 сент.

6 минут назад

Необходимо выполнить написание ВКР, тему готов обсудить

Диплом, Технология и организация строительного производства, строительство

Срок сдачи к 30 дек.

8 минут назад

Всё сказано на фото

Чертеж, Черчение

Срок сдачи к 20 сент.

8 минут назад

Рассчитать показатели по экономике

Решение задач, Экономика

Срок сдачи к 17 сент.

9 минут назад

Разработка приложения “Сортировка и слияние массивов(Пузырьковая...

Курсовая, Поддержка и тестирование программных модулей, информатика, программирование

Срок сдачи к 10 окт.

9 минут назад

Решение задач по технической механике

Решение задач, техническая механика

Срок сдачи к 17 сент.

12 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

Размещенные на сайт контрольные, курсовые и иные категории работ (далее — Работы) и их содержимое предназначены исключительно для ознакомления, без целей коммерческого использования. Все права в отношении Работ и их содержимого принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие в связи с использованием Работ и их содержимого.

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно