47643 (608326)

Файл №608326 47643 (Моделирование работы конечного распознавателя для последовательно-сти элементов типа "дата" в немецком формате, разделенных запятыми и заключённых в фигурные скобки)47643 (608326)2016-07-302016-07-30СтудИзба

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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Регистрация/авторизация

Текст из файла

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

Кафедра ВСиИ

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

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

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

Вариант № 15

Выполнил:

студент группы ИС-31

Мельников А.

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

2009 год

Содержание

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

Введение

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

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

3 Программное моделирование работы конечного автомата

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

5 Блок-схема

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

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

Моделирование работы конечного распознавателя для последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01.12.2001},{05.07.2003});

Введение

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

Теоретические сведения.

Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D, q₀, F), где

Q - конечное множество состояний;
T - конечное множество допустимых входных символов (входной алфавит);
D - функция переходов (отображающая множество Q(T {e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;
q₀ Q - начальное состояние управляющего устройства;
F Q - множество заключительных состояний.

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

Пусть M = (Q, T, D, q₀, F) - НКА. Конфигурацией автомата M называется пара (q, w) QT^*, где q - текущее состояние управляющего устройства, а w - цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q₀, w) называется начальной, а конфигурация (q, e), где q F - заключительной (или допускающей).

Пусть M = (Q, T, D, q₀, F) - НКА. Тактом автомата M называется бинарное отношение , определенное на конфигурациях M следующим образом: если p D(q, a), где a T {e}, то (q, aw) (p, w) для всех w T^*.

Будем обозначать символом ⁺ ( ^*) транзитивное (рефлексивно- транзитивное) замыкание отношения .

Говорят, что автомат M допускает цепочку w, если (q₀, w) ^*(q, e) для некоторого q F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е.

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

Пусть M = (Q, T, D, q₀, 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

Цф1

нет

Дб1

Дб2

нет

Дб2

нет

мес

нет

Цф1

Дб2

нет

денм

Дб1

Цф0

нет

Цф0

Дб2

нет

денф

Дб1

Цф3

нет

Цф3

Дб2

нет

мес

Мес0

Мес1

нет

Мес0

нет

месб

фев

месб

месм

месб

месм

месб

месм

нет

Мес1

месб

месм

месб

нет

месб

нет

денб

нет

месм

нет

денм

нет

дата

нет

год

нет

год

Цг1

нет

Цг1

Цг2

нет

Цг2

Цг3

нет

Цг3

Цг4

нет

Цг4

нет

да

нет

день

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

Характеристики

Тип файла

Документ

Размер

6,42 Mb

Материал

Тип материала

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

Предмет

Информатика

Учебное заведение

Неизвестно

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы

modelirovanie-raboty-konechnogo-raspoznavatelya-dlya-posledovatelno-sti-elementov-tipa-quotdataquot-v-nemeckom-formate-razdelennyh-zapyatymi-i-zaklyuchennyh-v-figurnye-skobki-1469857949-47643.zip

47643.rtf

Поделитесь ссылкой:

Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.

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

Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.

Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.

Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.

Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.

Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.

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

Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.

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

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

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