- •1 Постановка задачи
- •2 Индивидуальное задание. Построение праволинейной грамматики
- •3 Построение автоматной грамматики по праволинейной
- •4 Построение недетерминированног автомата
- •5 Сведение недетерминированного конечного автомата к детерминированному
- •6 Построение минимального автомата
- •7 Построение сети петри моделирующей работу распознающего автомата
- •9 Описание контрольного примера
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное учреждение высшего профессионального образования
«Ижевский государственный технический университет им. М.Т.Калашникова»
Кафедра АСОИУ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
по дисциплине «Математическая лингвистика»
на тему «Синтез распознающего автомата»
Выполнил: студент гр. Б04-782-1 Д.А.Шутов
Руководитель: ассистент каф.АСОИУ Д.Р.Касимов
Ижевск 2013
СОДЕРЖАНИЕ
СОДЕРЖАНИЕ……………………………………………………………………2
ВВЕДЕНИЕ………………………………………………………………………...3
1 ПОСТАНОВКА ЗАДАЧИ………………………………………………………4
2 ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ………………………………………………………………........5
3 ПОСТРОЕНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПО ПРАВОЛИНЕЙНОЙ………………………………………………………………6
4 ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО АВТОМАТА………….......7
5 СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ…………………………………………………....10
6 ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА………………………….13
7 ПОСТРОЕНИЕ СЕТИ ПЕТРИ МОДЕЛИРУЮЩЕЙ РАБОТУ РАСПОЗНАЮЩЕГО АВТОМАТА…………………………………………….16
8 ОПИСАНИЕ АЛГОРИТМА ПРОГРАММЫ РЕАЛИЗУЮЩЕЙ РАСПОЗНАЮЩИЙ АВТОМАТ………………………………………………..20
9 ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА………………………………..21
ЗАКЛЮЧЕНИЕ…………………………………………………………………...22
СПИСОК ЛИТЕРАТУРЫ………………………………………………………..23
ПРИЛОЖЕНИЕ А…………………………………………………………...…...24
ПРИЛОЖЕНИЕ Б..................................................................................................30
ВВЕДЕНИЕ
Проектирование распознающего автомата и его программная реализация необходимы при построении узлов цифровых вычислительных машин, при создании компиляторов, лингвистических процессоров и лексических анализаторов в трансляторах.
Конечный автомат - это абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Целью курсовой работы является изучение способов задания языков грамматиками, распознающими автоматами и сетями Петри, синтез и программная реализация конечного автомата, распознающего заданный язык.
1 Постановка задачи
Построить модель распознающего автомата на основе индивидуального задания.
Для этого необходимо на основе формальной грамматики получить праволинейную грамматику, построить ее граф. По праволинейной грамматики построить автоматную. Затем построить недетерминированный распознающий автомат, задать таблицу переходов для него и изобразить граф переходов. Перейти от недетерминированного к полностью определенному детерминированному автомату. Задать таблицу переходов и изобразить граф переходов для полученного автомата. Минимизировать этот автомат. Задать таблицу переходов и граф переходов для минимального автомата.
Получить граф переходов минимального автомата по праволинейной грамматике используя сети Петри. Сравнить полученную автоматную сеть с графом минимального автомата.
Входными данными для автомата является цепочка из терминальных символов. На выходе автомата появляется состояние, отвергающее или допускающее входную цепочку.
Задана формальная грамматика
G=<Vt, Vn, S, R>, где
Vt = {C1, C2,…, C18} - терминальный словарь,
Vn = {S, A, B, C, D, E, F} - нетерминальный словарь,
S - начальный символ грамматики, SVn,
P - множество правил вывода
Правила вывода имеют следующий вид:
Sc1 c2 c3 A; Sc1 c4 c5 B; Sc6 C; Sc7 F;
Ac8 D; Ac9; Bc8 E; Bc9; Cc8E; Cc9;
Dc10 S; Dc11; Ec10 S; Ec11;
Fc12 c13 c14 c15; Fc16 c13 c14 c15; Fc17 c18 c15.
2 Индивидуальное задание. Построение праволинейной грамматики
Индивидуальное задание формируется посредством занесения во вторую строчку таблицы 1.1 имени фамилии и отчества студента.
ci |
c1 |
c2 |
c3 |
c4 |
c5 |
c6 |
c7 |
c8 |
c9 |
c10 |
c11 |
c12 |
c13 |
c14 |
c15 |
c16 |
c17 |
c18 |
si |
Ш |
У |
Т |
О |
В |
|
Д |
М |
И |
Т |
Р |
И |
Й |
|
А |
Л |
Е |
К |
xi |
X2 |
X7 |
X5 |
X4 |
X2 |
X5 |
X6 |
X3 |
X3 |
X5 |
X0 |
X3 |
X0 |
X5 |
X5 |
X0 |
X6 |
X7 |
Таблица 1.1. Формирование варианта задания
Третья строчка заполняется с помощью таблицы 1.2.
А |
Б |
В |
Г |
Д |
Е |
Ж |
З |
И |
Й |
К |
Л |
М |
Н |
О |
П |
x1 |
x5 |
x2 |
x4 |
x6 |
x6 |
x4 |
x3 |
x3 |
x0 |
x7 |
x0 |
x3 |
x7 |
x4 |
x5 |
P |
С |
Т |
У |
Ф |
Х |
Ц |
Ч |
Ш |
Щ |
Ь |
Ы |
Э |
Ю |
Я |
_ |
x0 |
x4 |
x5 |
x7 |
x2 |
x5 |
x1 |
x2 |
x2 |
x0 |
x6 |
x1 |
x1 |
x3 |
x7 |
x5 |
Таблица 1.2. Соответствия
Заданная грамматика, являющаяся праволинейной, приводится к виду
G'=<V't, V'n, S, R'>, где V't={x0, …, x7} – новый терминальный словарь;
R' – множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V't в соответствии с таблицей 1.1. В моем варианте они имеют вид:
Sx2 x7 x5 A | x2 x4 x2 B | x5 C | x6 F;
Ax3 D | x3;
Bx3 E | x3;
Cx3 E | x3;
Dx5 S | x0;
Ex5 S | x0;
Fx3 x0 x5 x5 | x0 x0 x5 x5 | x6 x7 x5.
3 Построение автоматной грамматики по праволинейной
Для получения автоматной грамматики, необходимо заменить правила, у которых в правой части перед нетерминальным символом стоит более чем один терминальный, несколькими правилами.
Sx2 S1; S1x7 S2; S2x5 A;
Sx2 S3; S3x4 S4; S4x2 B;
Sx5 C;
Sx6 F;
Ax3 D; Ax3 A1; A1;
Bx3 E; Bx3 B1; B1;
Cx3 E; Cx3 C1; C1;
Dx5 S; Dx0 D1; D1;
Ex5 S; Ex0 E1; E1;
Fx3 F1; F1x0 F2; F2x5 F3; F3x5 F4; F4;
Fx0 F5; F5x0 F6; F6x5 F7; F7x5 F8; F8;
Fx6 F9; F9x7 F10; F10x5 F11; F11;