Страницу Назад
Поискать другие аналоги этой работы
250 Теория языков программирования и методы трансляции. Курсовая работа. Вариант №8ID: 166207Дата закачки: 30 Апреля 2016 Продавец: rt (Напишите, если есть вопросы) Посмотреть другие работы этого продавца Тип работы: Работа Курсовая Форматы файлов: Исполняемые фалы (EXE), Microsoft Word, VisualC++ Сдано в учебном заведении: СибГУТИ Описание: Написать программу для автоматического построения детерминированного конечного автомата (ДКА) по словесному описанию языка. Вход программы: алфавит языка, обязательная конечная подцепочка, цепочки для распознавания. Выход: построенный ДКА (все 5 элементов), результат проверки цепочек. Подробно: Язык задан своим алфавитом и обязательной конечной подцепочкой всех цепочек языка. В конечной подцепочке не должно находиться символов, не содержащихся в алфавите. В крайнем случае она может быть и пустой. Программа должна: 1. по предложенному описанию регулярного языка строить ДКА, распознающий этот язык, в том виде, как он рассматривался в теории, раздел 2.2.2; 2. с помощью построенного ДКА проверять вводимые пользователем цепочки на их принадлежность этому языку. ДКА должен быть полностью определённым. Функция переходов ДКА может изображаться в виде таблицы или графа, вариант вида её представления выбирается разработчиком. Наиболее простой способ построения такого ДКА состоит в том, чтобы сначала по описанию языка построить НКА (недетерминированный конечный автомат), а затем преобразовать его согласно рассмотренному в разделе 2.2.2 алгоритму. При выборе такого способа построения ДКА промежуточный результат в виде НКА необходимо также отображать на экране по просьбе пользователя. По желанию автора допускаются и другие способы построения ДКА. После построения ДКА пользователь может вводить произвольные цепочки для проверки их на принадлежность исходному языку. Разбор цепочек автоматом следует поэтапно отображать на экране в виде последовательной смены конфигураций в соответствии с лабораторной работой №2. Рассмотрим пример построения ДКА. Задан язык: алфавит {0,1,a,b} и обязательная конечная подцепочка «01ab». Анализируем задание: язык будет состоять из цепочек любой длины, заканчивающихся на «01ab», например {1a01ab, bb01ab, ba101ab, …}. Тогда ДКА должен иметь вид M(Q,{0,1,a,b},d,q0,F), множество состояний Q и заключительные состояния F определятся в процессе построения. Разберёмся с построением функции переходов d. Очевидно, что пустая цепочка в языке не содержится (поскольку есть непустая обязательная конечная цепочка). Сначала определимся с минимальной цепочкой языка – это «01ab», и построим для неё граф переходов. Если выбрать способ с предварительным построением НКА, то такой автомат выглядит очевидным образом. Сначала могут быть прочитаны любые символы алфавита в любом количестве, а затем конечная подцепочка: Недетерминированность автомата вызвана тем, что из начального состояния существует два перехода по одному символу алфавита (‘0’). Преобразуем построенный автомат в детерминированный. Для этого построим таблицу переходов: вход Исходную таблицу переходов отделим от остальной части жирной линией. Для упрощения процесса будем создавать не все возможные новые состояния, которые могут получиться в результате сочетаний исходных состояний, а только те, которые реально возникают при построении. Сначала это единственное состояние q0q1 – занесём его в таблицу. Затем последовательно появятся q0q2, q0q3, q0q4. Все состояния исходного автомата, кроме q0, оказались недостижимыми. . Удалим их. состояние a b c q0 {q0,q1} {q0} {q0} {q0} q1 – {q2} – – q2 – – {q3} – q3 – – – {q4} q4 – – – – q0q1 A {q0q1} {q0, q2} {q0} {q0} q0q2 B {q0q1} {q0} {q0q3} {q0} q0q3 C {q0q1} {q0} {q0} {q0, q4} q0q4 D {q0q1} {q0} {q0} {q0} Заключительным состоянием станут те, которые содержат q4, здесь такое состояние одно - D. Новая таблица переходов примет следующий вид: состояние a b c q0 {A} {q0} {q0} {q0} A {A} {B} {q0} {q0} B {A} {q0} {C} {q0} C {A} {q0} {q0} {D} D {A} {q0} {q0} {q0} Граф переходов построен по таблице: Q={q0,A,B,С,D }, F={D}. ДКА построен. Комментарии: - Состояние: Отлично - СибГУТИ - 2016 г Размер файла: 394,2 Кбайт Фаил: (.zip) ------------------- Обратите внимание, что преподаватели часто переставляют варианты и меняют исходные данные! Если вы хотите, чтобы работа точно соответствовала, смотрите исходные данные. Если их нет, обратитесь к продавцу или к нам в тех. поддержку. Имейте ввиду, что согласно гарантии возврата средств, мы не возвращаем деньги если вариант окажется не тот. -------------------
Скачано: 6 Коментариев: 0 |
||||
Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них. Опять не то? Мы можем помочь сделать! Некоторые похожие работы:Теория языков программирования и методы трансляции. Курсовая работа. Вариант 19.Курсовая работа по дисциплине: Теория языков программирования и методы трансляции. Вариант №09 Курсовая работа по дисциплине: Теория языков программирования и методы трансляции. вариант 1 Курсовая работа По дисциплине: Теория языков программирования и методы трансляции. Вариант №09. Курсовая работа по дисциплине: Теория языков программирования и методы трансляции. Вариант №5 КУРСОВАЯ РАБОТА по дисциплине «теория языков программирования и методы трансляции» Вариант №3. Курсовая работа по дисциплине: Теория языков программирования и методы трансляции. Вариант №7. Ещё искать по базе с такими же ключевыми словами. |
||||
Не можешь найти то что нужно? Мы можем помочь сделать! От 350 руб. за реферат, низкие цены. Спеши, предложение ограничено ! |
Вход в аккаунт:
Страницу Назад
Cодержание / Программирование / Теория языков программирования и методы трансляции. Курсовая работа. Вариант №8
Вход в аккаунт: