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

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



Исходные данные - цепочка символов. В нее входят символы из множества: {x1,x2,x3,x4,x5,x6,x7}.

Построим правильные цепочки:

 

. Sx7x6x6Ax7x6x6x6Dx7x6x6x6x3

1 5 12

Получаем цепочку: x7x6x6x6x3

2. Sx7x4x3Bx7x4x3x6Ex7x4x3x6x5S x7x4x3x6x5x4C x7x4x3x6x5x4x2

2 7 13 3 10

Получаем цепочку: x7x4x3x6x5x4x2

3. Sx4Cx4x6Ex4x6x5S x4x6x5x1F x4x6x5x1x5x1x3

3 9 13 4 17

Получаем цепочку: x4x6x5x1x5x1x3

4. Sx1Fx1x1x7x4x3

4 15

Получаем цепочку: x1x1x7x4x3

5. Sx1Fx1x3x7x4x3

4 16

Получаем цепочку: x1x3x7x4x3

 

Построим не правильные цепочки:

. Sx7x6x6Ax7x6x6x3

1

Получаем цепочку: x7x6x6x3

2. Sx4x6x1

Получаем цепочку: x4x6x1

3. Sx4Cx4x6E x4x6x4

3 9

Получаем цепочку: x4x6x4

9.3 Результаты расчета

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

 

1.x7x6x6x6x3

3610813

.x7x4x3x6x5x4x2

3410811013

.x4x6x5x1x5x1x3

1081117913

.x1x1x7x4x3

1125913

.x1x3x7x4x3

1125913

 

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

 

1.x7x6x6x3

361012

.x4x6x1

3412

.x4x6x4

10812

 

9.4 Результаты испытания программы

 

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

 

Таблица 7. Результаты тестирования программы

ЦепочкаПримечание x1x6x7x4x5Цепочка допускается x7x1x5x6Цепочка допускается x2Цепочка допускается x1x1x6x7x2Цепочка допускается x7x6x6x3Цепочка не допускается x4x6x1Цепочка не допускается x4x6x4Цепочка не допускается

ЗАКЛЮЧЕНИЕ

детерминированный автомат сеть петри программный

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

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

Грамматики и автоматы сопровождены графическими изображениями. Результаты минимизации автоматов с помощью теории автоматов совпали с результатами программы реализующей распознающий автомат. Результаты программной реализации удовлетворительны.

 

СПИСОК ЛИТЕРАТУРЫ

 

  1. Методические указания для самостоятельной работы студентов по дисциплине" Теория вычислительных процессов и структур ". Ч1/ Ижевск. гос.техн.университет; Сост. Сенилов М.А. ИжГТУ, 2000.
  2. ГОСТ 19.003 - 80. Схемы алгоритмов и программ. Обозначения условные графические // Единая система программной документации. - М. : Издательство стандартов, 1980. - 9с.
  3. ГОСТ 19.005 - 78. Общие требования к программным документам // Единая система программной документации. - М. : Издательство стандартов, 1980. - 2с.

Интернет сайты:www.wikipedia.org

 

ПРИЛОЖЕНИЯ

 

Приложение 1

 

ТЕКСТ ПРОГРАММЫ

 

Program Automat;

const

E=12;

Tabl:Array [1..13,0..7] of byte=

((E, 3, E, 10, E, E, E, 11),

(5, E, E, E, E, E, E, E),

(E, 4, 6, E, E, E, E, E),

(E, E, 10, E, E, E, E, E),

(E, E, E, E, E, E, 9, E),

(10, E, E, E, E, E, E, E),

(E, E, E, E, E, 9, E ,E),

(E, E, 1, E, E, 13, E, E),

(E, E, E, E, E, 13, E, E),

(E, E, E, E, 13, E, E, 8),

(7, 2, E, E, E, E, 2, E),

(E, E, E, E, E, E, E, E),

(E, E, E, E, E, E, E, E));

var X,S:byte;

Str:string;

Er:boolean;

BEGIN

Write(Введите цепочку: );

ReadLn(Str);

S:=1;

Er:=FALSE;

X:=1;

While (X<=Length(Str)) and (Not(Er)) Do

Begin

If (Str[X]=x)and(Str[X+1] in [0..7]) Then

S:=Tabl[S,Ord(Str [X+1])-Ord(0)] Else

Begin

WriteLn(Неверный входной символ);

S:=0;

Er:=TRUE;

End;

X:=X+2;

End;

Write(Цепочка );

If S<>13 Then Write(не );

WriteLn(допустима);.

 

Приложение 2

 

РЕЗУЛЬТАТЫ РАСЧЕТА НА ЭВМ КОНТРОЛЬНОГО ПРИМЕРА

 

Введите цепочку: x1x6x7x4x5

Цепочка допустима

Введите цепочку: x1x1x2x7x2 x3 x4

Цепочка не допустима

Введите цепочку: x3x7x2x7x0x5x5

Цепочка не допустима

Введите цепочку: x7x1x5x6

Цепочка допустима

Введите цепочку: x3x7x2x5x5

Цепочка не допустима

Введите цепочку: x5x3x7x5x5

Цепочка не допустима

Введите цепочку: x2

Цепочка допустима

s