Синтез распознающего автомата
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Исходные данные - цепочка символов. В нее входят символы из множества: {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/ Ижевск. гос.техн.университет; Сост. Сенилов М.А. ИжГТУ, 2000.
- ГОСТ 19.003 - 80. Схемы алгоритмов и программ. Обозначения условные графические // Единая система программной документации. - М. : Издательство стандартов, 1980. - 9с.
- ГОСТ 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
Цепочка допустима