Синтез распознающего автомата - Программирование, компьютеры и кибернетика курсовая работа

Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Министерство образования и науки РФ
ГОУ ВПО «Ижевский государственный технический университет»
«Теория языков программирования и методы трансляции»
2. Индивидуальное задание. Построение праволинейной
3. Построение автоматной грамматики по праволинейной
4. Построение недетерминированного конечного автомата
5. Сведение недетерминированного конечного автомата к детерминированному
6. Построение минимального автомата
7. Построение сети Петри, моделирующей работу распознающего автомата
8. Описание программы, реализующей распознающий автомаТ
Цель курсовой работы состоит в изучении способов задания языков грамматиками, распознающими автоматами и сетями Петри, построении модели конечного автомата, распознающего заданный язык и его программная реализация.
В наше время, конечные автоматы имеют широкое распространение в компиляторах языков, поэтому программная реализация конечного автомата приобретает высокое значение. Также они применяются для создания лингвистических процессоров, для описания и обработки формальных языков.
Каждый автомат имеет конечное число входов, воспринимающих информацию, изображаемую конечным числом символов из некоторого алфавита, и конечное число выходов для выдачи информации.
Выходная информация автомата зависит не только от входной информации, но и от внутреннего состояния автомата. Конечный автомат имеет конечное число состояний.
Автоматы часто представляют сетями. Для автомата характерен последовательный способ функционирования: автомат последовательно переходит из состояния в состояние с заданной функцией перехода и осуществляет очередной шаг.
Необходимо построить праволинейную грамматику на основе индивидуального задания и приведенного ниже определения формальной грамматики. Затем по праволинейной грамматике построить автоматную грамматику. Построить недетерминированный конечный автомат по полученной автоматной грамматике. Преобразовать недетерминированный конечный автомат в детерминированный. Минимизировать полученный автомат, построить таблицу и граф переходов минимального автомата.
Построить по праволинейной грамматике сеть Петри. Минимизировать ее - построить недетерминированную сеть. Построить детерменированную сеть Петри на основе недетерминированной. По полученной детерминированной сети Петри построить граф переходов минимального автомата. Сравнить с графом минимального автомата, полученным ранее.
Входными данными для автомата является цепочка (строки, вводимые с клавиатуры) из терминальных символов. На выходе автомата выдается состояние - отвергающее или допускающее входную цепочку.
Задана формальная грамматика G = , где
V t = {C 1 , C 2 ,…, C 18 } - терминальный словарь,
V n = {S, A, B, C, D, E, F}- нетерминальный словарь,
S - начальный символ грамматики, S V n ,
Правила вывода имеют следующий вид:
2. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ
Индивидуальным задание для курсовой работы являются две таблицы (см. табл., 1,2) и правила вывода R. необходимо поставить в соответствие терминальным символам C i грамматики G терминальные символы X i грамматики G'. Для этого во вторую строку таблицы 1 записываются первые 18 символов фамилии, имени и отчества с обязательными пробелами между ними. В третью строку необходимо занести для каждого из 18 символов строки символы из алфавита {X 0 , X 1, X 2, X3 , X 4, X 5, X 6, X 7 } в соответствии с таблицей 2.
Таблица 2. Таблица соответствия между буквами алфавита и терминальными символами грамматики G'
Правила вывода для G' получаются из правил вывода грамматики G заменой символов C i на соответствующие символы X i . При этом праволинейная грамматика приводится к следующему виду:
V t '= { X 0 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 } - терминальный словарь,
V n '= {S, A, B, C, D, E, F}- нетерминальный словарь,
S - начальный символ грамматики, S V n ,
R - множество правил вывода, получаемых из правил вывода R заменой символов C i на X i в соответствии с таблицей 1.
Получим следующие правила вывода праволинейной грамматики G':
Граф полученной грамматики представлен на рис. 1.
3. ПОСТРОЕНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПО ПРАВОЛИНЕЙНОЙ
Процедура перевода праволинейной грамматики в автоматную состоит из следующих пунктов:
1. Если имеется правила вида А, где - непустая терминальная цепочка, то ввести новый нетерминальный символ В и добавить правило Вe. Затем заменить каждое из правил вида A правилом AB.
2. Заменить каждое правило вида Aa 1 ...a n B, для n>1, на правила:
где: A i , для (1 < i< (n-1)) - новые нетерминальные символы.
3. Если имеется правила вида АB, то, во-первых, удалить правила BB (если таковые имеются), во-вторых, заменить их правилами вида: Aa, для всех A и a, для которых существуют правила AB и Ba.
Применив данную процедуру перевода к полученной праволинейной грамматике G', получим следующую автоматную грамматику:
4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА
Процедуру построения недетерминированного автомата по автоматной грамматике:
1. Входным множеством автомата будет терминальное множество грамматики;
2. Множеством состояний автомата будет нетерминальное множество грамматики, а в качестве начального состояния будет выступать начальный нетерминальный символ грамматики - S;
3. По правилу Z состояние Z будет допускающим;
4. Для всех правил грамматики по правилу A xB вводим в автомате переход из состояния A в состояние B по входу x
5. Чтобы получить полностью определенный автомат, вводим состояние ошибки - Er, и во все оставшиеся клетки записываем переход в состояние ошибки.
Результатом такого построения является недетерминированный автомат с одним начальным состоянием. Таблицей переходов полученного автомата является таблица 3.
6. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ
Процедура перехода от недетерминированного автомата к детерминированному:
1. Пометить первую строку таблицы переходов для АД множеством начальных состояний автомата АН.
2. По данному множеству состояний B, помечающему строку таблицы переходов автомата АД, для которой переходы еще не выполнены, вычислить те состояния АН, которые могут быть достигнуты из B с помощью каждого входного символа и поместить полученное множество состояний в состояние ячейки для автомата АД.
3. Для каждого нового множества, порожденного на шаге 2, посмотреть: имеется ли уже в АД строка, помеченная этим множеством, если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, то никаких действий не надо.
4. Если в таблице АД есть строка, для которой еще не вычислены переходы, то вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, то переходим к шагу 5.
5. Пометить строку как допускающее состояние АД, тогда и только тогда, когда она содержит допускающее состояние АН, иначе пометить как отвергающее.
6. Добавим состояние ошибки Er и во всех пустых клетках запишем переход в состояние ошибки.
Получим следующий детерминированный автомат (см. табл. 4).
Таблица 4. Детерминированный автомат
6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА
Для получения минимального автомата воспользуемся методом разбиения. Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества (блоки), такие, что неэквивалентные состояния попадают в разные блоки.
Условие подобия: состояния S и T должны быть либо оба допускающими, либо оба отвергающими.
Условие преемственности: для всех входных символов состояния S и T должны переходить в эквивалентные состояния, т.е. их преемники эквивалентны.
Сначала состояния разбиваются на 2 блока. Один содержит только допускающие, другой - отвергающие. Очевидно, никакое из состояний 1-го блока не эквивалентно ни одному состоянию второго блока, что следует из условия подобия. Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:
1. Если под действием какого-либо входного символа какая-то часть состояний данного блока переходит в состояния из другого блока, что нарушает условие преемственности, то необходимо разбить данный блок на части так, чтобы не нарушалось в одном блоке условие преемственности.
2. Необходимо повторять шаг 1 до тех пор, пока дальнейшее разбиение невозможно.
3. За один раз можно разбить только один блок.
6.1 Делим на группы допускающих, недопускающих состояний
P 0 ={{S, Y, S 2 , S 4 , A, B, C, D, E, F, F 1 , F 2 , F 3 , F 4 , F 5 , F 6 , F 7 , F 8 }, {Z}}
P 1 ={{A, B, C}, {S, Y, S 2 , S 4 , D, E, F, F 1 , F 2 , F 3 , F 4 , F 5 , F 6 , F 7 , F 8 },{Z}}
P 2 ={{A, B, C}, {F 8 ,F 5 ,F 2 ,S }, { C, F 4 , F 7 , B, A },{ Y, S 2 , F 1 , F 4 },{Z}}
P 3 ={A, B, C}, {F 8 ,F 5 ,F 2 ,S }, {C, F 4 , F 7 , B, A}, {F 1 }, {Y, S 2 },{Z}}
P 4 ={{A, B, C}, {F 8 ,F 5 ,F 2 ,S}, { C, F 4 , F 7 , B, A }, {S 2 }, {E}, {F 1 }, {Y },{Z}}
P 5 ={{A, B, C}, {F 8 ,F 5 ,F 2 ,S}, { C, F 4 , F 7 , B, A },{S 2 }, {E}, {S 4 },{D}, {F 1 }, {F 4 }, {Y},{Z}}
P 6 ={{A, B, C}, {F 8 ,F 5 ,F 2 ,S}, { C, F 4 , F 7 , B, A },{S 2 }, {E}, {S 4 },{D}, {F 1 }, {F 3 },{F 6 } {Y},{Z}}
Дальнейшее разбиение невозможно. Перейдем к новым обозначениям:
Граф переходов минимального автомата приведен на рис.3.
Рис. 3 Граф переходов минимального автомата
Для полученной в п.2 праволинейной грамматики построим сеть Петри. Это можно сделать, поставив в соответствие нетерминальным символам грамматики позиции сети Петри, а терминалам - переходы сети Петри. Будем помечать позиции и переходы соответствующими нетерминалами и терминалами. Если в правой части имеет место конкатенация терминалов (т.е. цепочка терминалов), то в сети Петри между переходами, помеченными терминалами, должны появиться дополнительные позиции, которые будут помечены символами левой части правила подстановки с верхними индексами 1,2…
При построении остальных фрагментов соответствующих последующим правилам подстановки, следует использовать ранее обозначенные позиции, но не переходы. Таким образом, позиции могут иметь несколько входящих и исходящих дуг, а переходы могут иметь в точности по одной входящей и не более чем по одной исходящей дуге. Исходящая дуга может отсутствовать, если в правой части правила подстановки отсутствует замыкающий нетерминал. Маркером или фишкой отмечается позиция, соответствующая начальному символу грамматики. Построим сеть Петри (рис.4)
Полученная сеть представляет собой автоматную сеть Петри. Позиции можно трактовать как состояния конечного автомата, а переходы - как входные символы. Для полноты соответствия сети Петри распознающему автомату введена заключительная позиция Z, в которую направлены дуги из всех переходов, ранее не имевших исходящих дуг.
Можно заметить, что в этой сети имеются идентичные фрагменты, которые можно склеить. Склеивая фрагменты с позициями S 1 , S 3 по входному переходу X 5 , устраняем недетерминированность сети. Это позволит произвести еще ряд склеек. Позиции A, B и C склеиваются по выходным переходам X 5 и X 1 , позиции D, E - по входному переходу x 5 и по выходному переходу X 6 . Функционирование сети не изменится, если склеить идентичные фрагменты: F 3 ,F 6 и F 8 ; F 2 и F 5 ; F 1 и F 4 . Этот этап соответствует минимизации числа состояний автомата. Получим эквивалентную детерминированную сеть следующего вида (см. рис.5):
Рис. 5 Эквивалентная детерминированная сеть Петри
Сравнив два графа (рис.3 и рис.6), можно увидеть, что они в точности совпадают.
8.ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ РАСПОЗНАЮЩИЙ АВТОМАТ
Для проверки правильности построенного конечного распознавателя, написана программа. Программа реализует работу распознающего автомата и производит распознавание вводимых с клавиатуры цепочек. Программа написана на языке TURBO PASCAL. Для проверки работоспособности необходимо откомпилировать файл automat.pas, далее запустить файл automat.exe.
Программа имитирует работу конечного автомата. Программа применяется для распознавания входных цепочек символов право-линейной грамматики.
Для функционирования программы необходима любая ЭВМ, имеющая
Для работы программы требуются следующие устройства:
объем свободной оперативной памяти не менее 10 Kb;
При сбоях в работе устройств, программа прекращает свою работу.
Программа не предусматривает возможности продолжения работы с определенного этапа.
В качестве входной информации выступают строки, вводимые с клавиатуры, состоящие из символов исходной грамматики и являющиеся строкой для распознавания. Информация о допустимости цепочек выводится на дисплей. Входные данные имеют формат: хАхВхС , где А, В, С - числа от 1 до 7.
Перечень сообщений, используемых в работе программы, представлен в таблице 6.
Выводится, если введенная цепочка является недопустимой
Выводится, если введенная цепочка является допустимой
Логику написанной программы иллюстрирует схема программы, представленная на рис. 7
Исходные данные - цепочка символов. В нее входят символы из множества: {x1,x2,x3,x4,x5,x6,x7}.
1. Sx 7 x 6 x 6 Ax 7 x 6 x 6 x 6 Dx 7 x 6 x 6 x 6 x 3
Получаем цепочку: x 7 x 6 x 6 x 6 x 3
2. Sx 7 x 4 x 3 Bx 7 x 4 x 3 x 6 Ex 7 x 4 x 3 x 6 x 5 S x 7 x 4 x 3 x 6 x 5 x 4 C x 7 x 4 x 3 x 6 x 5 x 4 x 2
Получаем цепочку: x 7 x 4 x 3 x 6 x 5 x 4 x 2
3. Sx 4 Cx 4 x 6 Ex 4 x 6 x 5 S x 4 x 6 x 5 x 1 F x 4 x 6 x 5 x 1 x 5 x 1 x 3
Получаем цепочку: x 4 x 6 x 5 x 1 x 5 x 1 x 3
Получаем цепочку: x 1 x 1 x 7 x 4 x 3
Получаем цепочку: x 1 x 3 x 7 x 4 x 3
Следующие цепочки являются допустимыми т.к. после прочтения любой из них автомат переходит в допускающее состояние:
Следующие цепочки являются не допустимыми т.к. после прочтения любой из них автомат переходит в не допускающее состояние:
Результаты испытания программы представлены в таблице 7. Результаты совпадают с рассчитанными, отсюда следует, что программа, реализующая работу конечного автомата, работает правильно.
Таблица 7. Результаты тестирования программы
детерминированный автомат сеть петри программный
В ходе выполнения курсовой работы была построена праволинейная грамматика и ее граф. В дальнейшем по ней была построена автоматная грамматика, из которой в свою очередь был построен недетерминированный конечный автомат. Недетерминированный конечный автомат был сведен к эквивалентному детерминированному. Я произвела минимизацию детерминированного автомата методом разбиения.
Была построена сеть Петри, моделирующая работу распознающего автомата. В результате устранения в ней идентичных фрагментов была получена детерминированная сеть Петри.
Грамматики и автоматы сопровождены графическими изображениями. Результаты минимизации автоматов с помощью теории автоматов совпали с результатами программы реализующей распознающий автомат. Результаты программной реализации удовлетворительны.
Методические указания для самостоятельной работы студентов по дисциплине" Теория вычислительных процессов и структур ". Ч1/ Ижевск. гос.техн.университет; Сост. Сенилов М.А. ИжГТУ, 2000.
ГОСТ 19.003 - 80. Схемы алгоритмов и программ. Обозначения условные графические // Единая система программной документации. - М. : Издательство стандартов, 1980. - 9с.
ГОСТ 19.005 - 78. Общие требования к программным документам // Единая система программной документации. - М. : Издательство стандартов, 1980. - 2с.
Интернет сайты: www . wikipedia . org
Введите цепочку: x 1 x 6 x 7 x 4 x 5
Введите цепочку: x 1 x 1 x 2 x 7 x 2 x 3 x 4
Введите цепочку: x 3 x 7 x 2 x 7 x 0 x 5 x 5
Введите цепочку: x 3 x 7 x 2 x 5 x 5
Введите цепочку: x 5 x 3 x 7 x 5 x 5
Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера. курсовая работа [903,9 K], добавлен 14.07.2012
Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем. дипломная работа [1,8 M], добавлен 18.08.2013
Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера. курсовая работа [674,9 K], добавлен 13.06.2012
Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму. курсовая работа [997,7 K], добавлен 28.03.2011
Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции. контрольная работа [141,5 K], добавлен 14.10.2012
Составление формальной грамматики, недетерминированный конечный автомат. Построение конечного автомата, программное моделирование работы конечного автомата. Граф детерминированного автомата, Синтаксическая диаграмма. Блок-схемы, примеры разбора строк. курсовая работа [486,2 K], добавлен 19.11.2010
Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench. курсовая работа [964,2 K], добавлен 20.07.2015
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Синтез распознающего автомата курсовая работа. Программирование, компьютеры и кибернетика.
Типы Сочинений По Литературе
Методика Анализа Отчета О Финансовых Результатах Курсовая
Практическое задание по теме Реалізація лінійної структури програми мовою С++
Реферат: Риск ликвидности банка
Реферат На Тему Витамин В6
М Карамзин Бедная Лиза Сочинение
Контрольная Работа На Тему Радиометрическая И Радиохимическая Экспертиза
Курсовая работа: Cкремблирование и дескремблирование линейного сигнала. Скачать бесплатно и без регистрации
Дипломная работа по теме Особенности взаимосвязи просроченной задолженности и финансового результата кредитной организации
Контрольная Работа На Тему Психологический Эксперимент Как Специфический Метод Исследования
Реферат: Why I Hate The Mall Essay Research
Реферат по теме Державний лад СРСР в 1922-1992 рр.
Контрольная работа: Формы организации внешнеэкономической службы. Эффективность внешнеторговой деятельности предприятия
Реферат по теме Новгород
Курсовая работа по теме Анализ планирования выручки на примере ООО 'Мир окон и дверей'
Курсовая Работа На Тему Риторика Как Наука. Предмет, Структура И Функции
Эссе Проблемы Современного Мира
Полупроводниковый Диод Лабораторная Работа
Сочинение По Упр 102 8 Класс Презентация
Доклад по теме Роль государственной Думы в истории становления Российской государственности
Маркетингова політика комунікацій - Маркетинг, реклама и торговля реферат
Соотношение конституционного и международного права - Государство и право статья
Способы и механизмы защиты интеллектуальной собственности - Государство и право курсовая работа