Построение распознователя грамматик. Построение распознавателя для заданной грамматики и реализация е. Курсовая работа по дисциплине "Основы дискретной математики"
Скачать 227 Kb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ КАФЕДРА КОМПЬЮТЕРНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ Курсовая работа по дисциплине "Основы дискретной математики" Тема: "Построение распознавателя для заданной грамматики и реализация его в виде программы, которая проверяет вводимые пользователем цепочки" 2006 Задание на курсовую работупо дисциплине "Основы дискретной математики"Задание на выполнение работы: 1. Роль информационных технологий в быту современного человека. 2. Подробная справка по теоретическим аспектам формальных грамматик и их преобразованию. 3. Выполнить исследование и преобразование исходной грамматики: G [Q] = (VT = {a, b,h}; VN = { Q, A, B, H }; P = { Q a Q H; Q b a h A; A a b B h; H bB; B a b b H h; H }) ( - пустая цепочка). Построить распознаватель для преобразованной грамматики и реализовать его в виде программы, которая проверяет текстовые файлы и вводимые пользователем цепочки. Работу необходимо выполнить в соответствии с графиком и требованиями к выполнению курсовой работы по основам дискретной математики; Изменение и уточнение темы с согласия преподавателя возможно только на первом этапе работы; Готовая работа сдается на проверку не позже, чем за день до защиты. РефератКурсовая работа по дисциплине "Основы дискретной математики" на тему: "Построение М П-распознавателя для задаваемой пользователем произвольной грамматики" содержит 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 в основном поддерживали крупные университеты и промышленные предприятия, то сегодня все больше людей хотят получать информацию прямо из дома, а не только со своего рабочего места. |