Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Архив1 / Курсовая(8).docx
Скачиваний:
32
Добавлен:
23.07.2013
Размер:
760.14 Кб
Скачать

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное учреждение высшего профессионального образования

«Ижевский государственный технический университет им. М.Т.Калашникова»

Кафедра АСОИУ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине «Математическая лингвистика»

на тему «Синтез распознающего автомата»

Выполнил: студент гр. Б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 - множество правил вывода

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

Sc1 c2 c3 A; Sc1 c4 c5 B; Sc6 C; Sc7 F;

Ac8 D; Ac9; Bc8 E; Bc9; Cc8E; Cc9;

Dc10 S; Dc11; Ec10 S; Ec11;

Fc12 c13 c14 c15; Fc16 c13 c14 c15; Fc17 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. В моем варианте они имеют вид:

Sx2 x7 x5 A | x2 x4 x2 B | x5 C | x6 F;

Ax3 D | x3;

Bx3 E | x3;

Cx3 E | x3;

Dx5 S | x0;

Ex5 S | x0;

Fx3 x0 x5 x5 | x0 x0 x5 x5 | x6 x7 x5.

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

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

Sx2 S1; S1x7 S2; S2x5 A;

Sx2 S3; S3x4 S4; S4x2 B;

Sx5 C;

Sx6 F;

Ax3 D; Ax3 A1; A1;

Bx3 E; Bx3 B1; B1;

Cx3 E; Cx3 C1; C1;

Dx5 S; Dx0 D1; D1;

Ex5 S; Ex0 E1; E1;

Fx3 F1; F1x0 F2; F2x5 F3; F3x5 F4; F4;

Fx0 F5; F5x0 F6; F6x5 F7; F7x5 F8; F8;

Fx6 F9; F9x7 F10; F10x5 F11; F11;

Соседние файлы в папке Архив1