Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.
Краткое сожержание материала:

Размещено на

Размещено на

Федеральное агентство по образованию

ГОУ ВПО «Ижевский государственный технический университет»

факультет «Информатика и вычислительная техника»

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

к курсовой работе по дисциплине

«Теория языков программирования и методы трансляции»

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

Выполнил

студент гр. 4-78-10 Протозанов Е.С.

Принял

д.т.н., профессор Сенилов М.А.

Ижевск 2011г.



ВВЕДЕНИЕ

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

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

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

1. ПОСТАНОВКА ЗАДАЧИ

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

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

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

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

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

G = <Vt, Vn, S, P>

Где Vt = {C1, C2,…, C18} - терминальный словарь,

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

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

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 -> C8 E;	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. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ

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

Грамматика G приводится к виду

G'=<V't, V'n, S, R'>

Где V'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 -> 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;

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