МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
КАФЕДРА
КОМПЬЮТЕРНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Курсовая работа
по дисциплине
"Основы дискретной математики"
Тема: "Построение распознавателя для заданной грамматики и реализация его в виде программы, которая проверяет вводимые пользователем цепочки"
2006
Задание на выполнение работы:
1. Роль информационных технологий в быту современного человека.
2.Подробная справка по теоретическим аспектам формальных грамматик и их преобразованию.
3.Выполнить исследование и преобразование исходной грамматики:
G [Q] = (VT = {a, b,h}; VN = { Q, A, B, H }; P = { Q-aQH;
Q - b a h A; A - a b B h; H - bB; B - a b b H h; H -e }) (e - пустая цепочка).
Построить распознаватель для преобразованной грамматики и реализовать его в виде программы, которая проверяет текстовые файлы и вводимые пользователем цепочки.
Работу необходимо выполнить в соответствии с графиком и требованиями к выполнению курсовой работы по основам дискретной математики;
Изменение и уточнение темы с согласия преподавателя возможно только на первом этапе работы;
Готовая работа сдается на проверку не позже, чем за день до защиты.
Курсовая работа по дисциплине "Основы дискретной математики" на тему: "Построение М П-распознавателя для задаваемой пользователем произвольной грамматики" содержит 21 страницу машинописного текста, 5 рисунков, 3 таблицы, страниц приложения.
В работе рассмотрен один из разделов дискретной математики - "Классификация грамматик; эквивалентные преобразования КС-грамматик", разработан программный продукт, с помощью которого можно проверить задаваемую пользователем грамматику и упростить ее с помощью эквивалентных преобразований правил.
Ключевые слова:
дискретная математика, КС-грамматика, S-грамматика, правило грамматики; терминальный символ; нетерминальный символ; дерево вывода; эквивалентные преобразования; сентенциальная форма.
Роль информационных технологий в быту современного человека.
За последние несколько лет человечество совершило удивительный рывок в области развития компьютерных, и вследствие этого, информационных технологий. Всего каких-то десять лет назад среднестатистический гражданин не мог и мечтать о собственном персональном компьютере. В середине 80-х годов ЭВМ были прерогативой крупных предприятий, обслуживание этих машин осуществлялось через разветвленную сеть специализированных сервисных центров. Зачастую многие предприятия не имели достаточно квалифицированных кадров для монтажа и обслуживания своих ЭВМ. Соответственно и проблемы связи между вычислительными комплексами вставали в узком кругу специалистов. Несмотря на то, что первые экспериментальные сети передачи пакетов данных были созданы в 1961 году Defence Advanced Research Agency (DARPA) по заданию министерства обороны США, в нашей стране они применялись лишь в отдельных отраслях народного хозяйства и в военной области.
Технологический скачок последнего десятилетия, особенно показательный в области компьютерных технологий, позволил разработать серию современных персональных компьютеров. Микро ЭВМ постепенно начали входить в нашу повседневную жизнь. Согласно журналу "Мир Internet" в России в частном пользовании находится более 50 тыс. персональных компьютеров. Новейшие технологии компаний IBM, Intel сделали возможным разработку мощных, многофункциональных персональных ЭВМ, экономически доступных среднему и нижне-среднему классу граждан. Компьютерные и информационные технологии уверенно входят в нашу жизнь. Сейчас персональные ЭВМ можно встретить не только в офисах крупных и мелких фирм, на производстве и в учебных заведениях, компьютеры все чаще можно встретить дома у инженеров и школьников, ученых и бизнесменов.
Персональная ЭВМ давно превратилась в предмет труда, ни одно предприятие не обходится без электронной базы данных, без современных средств коммуникаций, мощных вычислительных средств. Не менее важную роль играют ЭВМ и в быту современного россиянина. Функции домашнего компьютера разнообразны. Он позволяет осуществлять не только производственный процесс на дому, но и целый ряд всевозможных процессов. Современные разработки позволяют осуществлять управление электрическими бытовыми приборами, принимать радио и телепередачи, компьютер в сопряжении со сканером и принтером является фактически домашним офисом, позволяющим выполнять обработку любой текстовой или графической информации. Рекреационная роль персональных домашних компьютеров не может быть обойдена стороной. Многочисленные компьютерные игры позволяют организовать досуг в соответствии с интересами конкретного человека. Мультимедийные приложения могут намного облегчить усвоение учебного материала как студентам и школьникам, так и все жаждущим самообразования.
Отдельного упоминания заслуживает информационная составляющая компьютерных технологий. По данным ЮНЕСКО к 1950 г. количество информации, которой оперировало общество, удваивалось за десять лет, к 70 г. - за пять лет, к 1980 - за два года, с начала 90-х количество информации удваивается за год. В настоящее время до 80% трудоспособного населения тем или иным образом профессионально задействованы в области получения, распространения или обработки информации. Средства распространения информационных потоков так же претерпели значительную эволюцию. Средства теле и радио связи вошли в каждый дом, печатные издания доступны подписчикам по всему миру. Однако новые реалии времени представляют новые требования и к способам распространения и обработки информации. Возьмем на себя смелость утверждать, что средства электронной связи с использованием новейшей вычислительной техники представляют на сегодняшний день наилучшие возможности в области распространения и обработки информационных потоков. Всемирная компьютерная сеть Internet является наиболее известным носителем информации. Internet - глобальная компьютерная сеть, охватывающая весь мир. Сегодня Internet имеет около 15 миллионов абонентов в более чем 150 странах мира. Ежемесячно размер сети увеличивается на 7-10%. Все больше людей обращаются к услугам электронной почты, дающей возможность пересылки текстовой, графической, практически любого вида информации или данных в любую точку мира за считанные минуты. Базы данных, сервера специализированной информации, телеконференции, файловые сервера, в настоящее время уже трудно представить жизнь современного специалиста или ученого без этих нововведений. Уже имеются разработки, обещающие множество новых возможностей, среди них Internet-телефония, передача видео и графической информации.
Стремительное развитие научно-технического прогресса предъявляет новые требования и к качеству информатизации общества. Мы считаем особенно важным развитие именно информационной составляющей компьютерных технологий. На сегодняшний день это наиболее важная и наиболее динамически развивающаяся отрасль народного хозяйства России и промышленности всего мира. Особенно важным, несомненно, является совершенствование инфраструктуры систем связи. Если раньше глобальную сеть Internet в основном поддерживали крупные университеты и промышленные предприятия, то сегодня все больше людей хотят получать информацию прямо из дома, а не только со своего рабочего места.
В расширенном представлении под термином "язык" понимают всякое средство общения, состоящее из:
- знаковой системы, т.е. множества допустимых последовательностей знаков;
- множества смыслов этой системы;
- соответствия между последовательностями знаков и смыслами, делающими осмысленными допустимые последовательности знаков.
Знаками могут быть буквы алфавита, математические обозначения, звуки, ритуальные действия и т.д. Hаука об осмысленных знаковых системах называется семиотикой. Hаиболее исследованными являются знаковые системы, у которых знаками являются символы алфавита. Правила, определяющие множество текстов (допустимых последовательностей знаков), образуют синтаксис языка; описание множества смыслов и соответствия между текстами и смыслами - семантику языка. К таким знаковым системам относятся естественные языки, языки различных областей науки, языки программирования.
Семантика языка существенно зависит от назначения языка, в то время, как для синтаксиса можно сформулировать понятия и методы, не зависящие от назначения и целей языка. Для исследования синтаксиса сложился специальный математический аппарат - теория формальных грамматик, в котором язык понимается уже не как средство общения, а как множество формальных объектов - последовательностей символов алфавита. Эти последовательности называют цепочками и язык понимают как множество цепочек.
Пусть задан алфавит V, в котором можно построить множество V* (читается - итерация алфавита V) цепочек. Формальный язык L в алфавите V- это подмножество цепочек из V* (LÌV*). Описание формальных языков осуществляется с помощью формальных порождающих грамматик (формальных грамматик).
Формальная порождающая грамматика G (в дальнейшем - грамматика G) - это формальная система, определяемая четверкой объектов:
G [Z] = (VN, VT, Z, P),
где VN - алфавит нетерминалов (вспомогательных символов);
VT - алфавит терминалов (основных символов);
Z - начальный символ (аксиома) грамматики;
P - конечное множество правил.
Hетерминалы принято обозначать большими буквами латинского алфавита, терминалы - малыми буквами. В алфавит нетерминалов обязательно входит начальный символ грамматики.
Каждое правило из множества P имеет вид x - y, - где x, y цепочки, состоящие из терминальных и нетерминальных символов. В дальнейшем будем рассматривать грамматики, содержащие только правила, левые части которых состоят из одного нетерминального символа (контекстно-свободные грамматики). При этом должно быть хотя бы одно правило, левая часть которого - начальный символ грамматики.