Навигация:

Главная Случайная страница Обратная связь ТОП Интересно знать Избранные Новые материалы

Топ:

Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...

Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...

Оснащения врачебно-сестринской бригады.

Интересное:

Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...

Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...

Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...

Дисциплины:

Автоматизация Антропология Археология Архитектура Аудит Биология Бухгалтерия Военная наука Генетика География Геология Демография Журналистика Зоология Иностранные языки Информатика Искусство История Кинематография Компьютеризация Кораблестроение Кулинария Культура Лексикология Лингвистика Литература Логика Маркетинг Математика Машиностроение Медицина Менеджмент Металлургия Метрология Механика Музыкология Науковедение Образование Охрана Труда Педагогика Политология Правоотношение Предпринимательство Приборостроение Программирование Производство Промышленность Психология Радиосвязь Религия Риторика Социология Спорт Стандартизация Статистика Строительство Теология Технологии Торговля Транспорт Фармакология Физика Физиология Философия Финансы Химия Хозяйство Черчение Экология Экономика Электроника Энергетика Юриспруденция

Построение автоматной грамматики по праволинейной

2020-04-01

459

0.00 из 5.00 0 оценок

Заказать работу

Стр 1 из 3Следующая ⇒

Введение

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

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

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

1.
Постановка задачи

Построить модель распознающего автомата на основе индивидуального задания.

Для этого необходимо на основе формальной грамматики получить праволинейную грамматику, построить ее граф. По праволинейной грамматики построить автоматную. Затем построить недетерминированный распознающий автомат, задать таблицу переходов для него и изобразить граф переходов. Перейти от недетерминированного к полностью определенному детерминированному автомату. Задать таблицу переходов и изобразить граф переходов для полученного автомата. Минимизировать этот автомат. Задать таблицу переходов и граф переходов для минимального автомата.

Получить граф переходов минимального автомата по праволинейной грамматике используя сети Петри. Сравнить полученную автоматную сеть с графом минимального автомата.

Входными данными для автомата является цепочка из терминальных символов. На выходе автомата появляется состояние, отвергающее или допускающее входную цепочку.

Задана формальная грамматика

G = <V_t, V_n, S, P>, где

V_t = {C₁, C₂,…, C₁₈} - терминальный словарь,

V_n = {S, A, B, C, D, E, F} - нетерминальный словарь,

S - начальный символ грамматики, S V_n,

P - множество правил вывода

Правила вывода имеют следующий вид:

S -> C₁ C₂ C₃ A; S -> C₁ C₄ C₅ B; S -> C₆ C; S -> C₇ F; A -> C₈ D; A -> C₉; B -> C₈ E; B -> C₉; C -> C₈ E; C -> C₉; D -> C₁₀ S; D -> C₁₁; E -> C₁₀ S; E -> C₁₁; F -> C₁₂ C₁₃ C₁₄ C₁₅; F -> C₁₆ C₁₃ C₁₄ C₁₅; F ->C₁₇C₁₈C₁₅.

2. Индивидуальное задание. построение праволинейной грамматики

праволинейный грамматика автомат программа

Индивидуальным заданием является грамматика G', порождаемая из заданной формальной грамматики G.

Грамматика Gприводится к виду G'=<V't, V'n, S, R'>, где't={x0, x1, …, x7} - новый терминальный словарь, получаемый из Vt заменой ciна xiв соответствии с таблицей 1.

Таблица 1

ci c1 c2 c3 с4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15 c16 c17 c18

si П Р О Т О З А Н О В _ Е В Г Е Н И Й

xi x5 x0 x4 x5 x4 x3 x1 x7 x4 x2 x5 x6 x2 x4 x6 x7 x3 x0

R' - множество правил вывода, получаемых из множества R, путем замены символов алфавита Vtсимволами алфавита V't, в соответствии с таблицей 1. Таблица 1 заполняется следующим образом: во вторую строку таблицы 1 заносятся имя фамилия и отчество, с обязательными пробелами между ними.

Третья строка таблицы 1 заполняется в соответствии с таблицей 2.

Таблица 2

А Б В Г Д Е Ж З И Й К Л М Н О П

x1 х5 x2 x4 x6 x6 x4 x3 x3 x0 x7 x0 x3 x7 x4 x5

P С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я _

x0 х4 x5 x7 x2 x5 x1 x2 x2 x0 x6 x1 x1 x3 x7 x5

В результате, множество правил вывода праволинейной грамматики G' имеет вид:

1) S ->x5x0x4A; 2) S -> x5 x5 x4 B; 3) S -> x3 C; 4) S -> x1 F; 5) A -> x7 D; 6) A -> x4; 7) B -> x7 E; 8) B -> x4; 9) C -> x7 E; 10) C -> x4; 11) D -> x2 S; 12) D -> x5; 13) E -> x2 S; 14) E -> x5; 15) F -> x6 x2 x4 x6; 16) F -> x7 x2 x4 x6; 17) F ->x3x0x6;

Построим граф грамматикиG' (рис. 1).

Граф грамматики G’

Рис. 1

Построение сети Петри

Построим для грамматики G' сеть Петри. Для этого, поставим в соответствие нетерминальным символам позиции (кружки) сети. А терминалам - переходы (планки) сети. Пометим позиции и переходы соответствующими нетерминалами и терминалами.

Позиции соединяются дугами только через переходы, а переходы - через позиции. Если в правой части некоторого правило вывода из R’ имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появляться дополнительные позиции, которые можно помечать символами левой части правил вывода с индексами 1, 2, ….

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

Выполнив эти действия, получаем сеть Петри (рис. 5).

Сеть Петри

Рис. 5

Для полноты соответствия построенной сети Петри распознающему автомату Мура, введем не показанную на рис. 5 заключительную позицию Z, в которую направим дуги из всех переходов, ранее не имевших исходящих дуг. В результате получим новую сеть Петри (рис. 6).

Сеть Петри с заключительной позицией Z

Рис. 6

Далее, необходимо минимизировать сеть Петри. Для этого определим в ней идентичные фрагменты. Итак, идентичными фрагментами являются позиции D и E c инцидентными им переходами x5 и x4. Также, позиции A, Bи С с инцидентными им переходами x4 и x7. Позиции S1 и S3, F2 и F5, F3 и F6, F1 и F4, F6 и F8можно склеить попарно. В результате получаем минимизированную недетерминированную сеть Петри (рис. 7).

Минимизированная сеть Петри

Рис. 7

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

Недетерминированность устраняется склеиванием двух позиций P_l и P_k в одну (P_l, P_k). При этом позиции (P_l, P_k) инцидентны все исходящие дуги, являющиеся исходящими дугами позиций P_lиP_k.

В полученной сети Петри отсутствуют позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами. А значит, сеть Петри (рис. 7) уже детерминированаи минимизирована.

Теперь обозначим позиции сети Петри следующими буквами:

S -> A S1, S3 -> B F ->C F7 ->D F2, F5 ->E F1, F4 ->F

S2, S4->G D, E->H A, B, C->I F3, F6, F8 ->J Z->K

Уберем переходы из сети Петри, дуги подпишем терминалами переходов, тогда получим граф переходов (рис. 8).

Граф переходов, полученный из сети Петри

Рис. 8

Сравнив полученный граф (рис. 8) с графом минимального автомата (рис. 4) мы видим, что они идентичны. Значит, минимальный автомат построен правильно.

Вводная часть

Программа: машина Тьюринга

Обозначение программы: turing.exe

Программа используется для построения моделей машины Тьюринга

Функциональное назначение

Программа предназначена для моделирования работы машины Тьюринга. Программа обрабатывает цепочку входных символов согласно правилам грамматики, записанным в виде таблицы переходов, и устанавливает состояние, позволяющее определить допустимость цепочки.

Системные требования

1. Операционная система семейства Windows, Linuxили MacOSс графическим фреймворком Qtверсии не менее 4.0

. Оперативная память не менее 32 мегабайт

. 10 мегабайт места на жестком диске

Описание входных данных

В настройках программы задается следующая информация:

. Таблица переходов конечного автомата

. Множество состояний машины

. Множество входных символов

. Пустой символ ленты

. Конечные состояния машины

. Допустимые состояния машины

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

Для допуска строки вводится дополнительное состояние, не являющеся состоянием минимального автомата, но требуемое для окончания работы машины Тьюринга с допускающим результатом.

9. Описание контрольного примера

Назначение

Контрольный пример необходим для тестирования программной реализации автомата - программы «turing».

Исходные данные

Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата: {x0, x1, x2, x3, x4, x5, x6, x7}.

Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики. Для проверки правильности работы автомата нужно проверить его с помощью допустимых цепочек. Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символS. Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал. Выписать терминальные символы из этого правила и если в конце стоит нетериманл, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.

Итак, получаем допускающие цепочки:

1) S ->x5x5x4B ->x4 - допустить

2 8

отсюда получаем цепочку: x5x5x4x4;

2) S ->x3C ->x7E ->x5-допустить

3 9 14

цепочка: x3 x7 x5;

3) S ->x1F ->x3x0x6 - допустить

4 17

цепочка: x1x3x0 x6;

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

Недопустимые цепочки:

4) x5 x5 x4

5) x3 x7

) x1 x3 x0

Заключение

В ходе данной работы было выполнено построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Автоматы, полученные двумя способами, идентичны, что говорит о правильности выполнения вычислений.

Для автоматизированной обработки входных последовательностей была реализована машина Тьюринга с устанавливаемым автоматом. Проверка теоретически построенных допустимых и недопустимых последовательностей показала, что программа работает верно.

Список литературы

1. Методические указания для самостоятельной работы студентов по дисциплине «Теория вычислительных процессов и структур». Ч1/ Ижевск. гос. техн. университет; Сост. Сенилов М.А. ИжГТУ, 2000.

2. ГОСТ 19.005 - 78. Общие требования к программным документам // Единая система программной документации. - М.: Издательство стандартов, 1980. - 2 с.

Введение

1.
Постановка задачи

Построение автоматной грамматики по праволинейной

Процедура перевода праволинейной грамматики в автоматную.

Праволинейная грамматика:

1) S -> x5 x0 x4 A; 2) S -> x5 x5 x4 B; 3) S -> x3 C; 4) S -> x1 F; 5) A -> x7 D; 6) A -> x4; 7) B -> x7 E; 8) B -> x4; 9) C -> x7 E;10) C -> x4; 11) D -> x2 S; 12) D -> x5; 13) E -> x2 S; 14) E -> x5; 15) F -> x6 x2 x4 x6; 16) F -> x7 x2 x4 x6; 17) F -> x3 x0 x6;

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

В результате замены правил, были получены следующие правила:

1.1) S ->x5 S1;

) S1 ->x0S2;

1.3) S2 ->x4A;

) S ->x5S3;

) S3 ->x5S4;

) S4 ->x4B;

) A ->x4 A1;

) A1 ->;

) B ->x4 B1;

) B1 ->;

) C ->x4C1;

) C1 ->;

12.1) D ->x2D1;

) D1 ->;

) E ->x2E1;

14.2) E1 ->;

15.1) F ->x6 F1;

15.2) F1 ->x2F2;

15.3) F2 ->x4 F3;

15.4) F3 ->x6 F4;

15.5) F4 ->?;

16.1) F -> x7 F5;

16.2) F5 -> x2F5;

16.3) F6 -> x4 F6;

16.4) F7 ->x6F8;

16.5) F8 ->;

17.1) F ->x3F9;

17.2) F9 ->x0F10;

17.3) F10 ->x6F11.

17.4) F11 ->;

Витогеполучаемследующуюавтоматную грамматику:

1.1) S -> x5 S1;

) S1 -> x0 S2;

) S2 -> x4 A

) S -> x5 S3

) S3 -> x5 S4

) S4 -> x4 B

) S -> x3 C;

) S -> x1 F;

) A -> x7 D;

) A -> x4 A1;

) A1 ->;

) B -> x7 E;

) B -> x4 B1;

) B1 ->;

) C -> x7 E;

) C -> x4 C1;

10.2) C1 ->;

) D ->x2 S;

) D ->x2 D1;

) D1 ->;

) E ->x2 S;

) E ->x2 E1;

) E1 ->;

) F ->x6 F1;

) F1 ->x2 F2;

) F2 ->x4 F3;

) F3 ->x6 F4;

) F4 ->;

) F -> x7 F5;

) F5 -> x2 F5;

) F6 -> x4 F6;

) F7 -> x6 F8;

) F8 ->;

) F -> x3 F9;

17.2) F9 -> x0 F10;

) F10 -> x6 F11;

) F11 ->;

12 3 Следующая ⇒

Поделиться с друзьями:

Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...

Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...