7 Построение сети петри моделирующей работу распознающего автомата
Сеть на рисунке 7.1 представляет собой не что иное, как автоматную сеть Петри (подкласс сетей Петри) и что позиции можно трактовать как состояния конечного автомата, а переходы - как входные символы. Для полноты соответствия построенной сети Петри распознающему автомату введем заключительную позицию Z.
Рисунок
7.1 Исходная сеть Петри
Теперь следует заметить, что в сети на рисунке 7.1 имеются три идентичных фрагмента, содержащие позиции A, B и C, каждой из которых инцидентны по два выходных перехода x2 и x6, два идентичных фрагмента с позициями D и E, каждой из которых инцидентен выходной переход x7. Фрагменты S1,S3; F1,F4; F2,F5; F3,F6,F8 c выходными переходами x4; x7; x0; x5 соответственно.
Рисунок 7.2. Недетерминированная сеть Петри.
Источником недетерминированности, очевидно, могут являться лишь позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами. Способ устранения недетерминированности виден из рисунка 7.3.
Рисунок 7.3. Детерминированная сеть Петри
Можно увидеть соответствие графа переходов минимального автомата и сети Петри, показав на сети Петри обозначение состояний минимального автомата(Рисунок 7.4)
Рисунок
7.4 Сеть Петри с состояниями минимального
автомата.
8 ОПИСАНИЕ ПРОГРАММЫ РЕАЛИЗУЮЩЕЙ РАСПОЗНАЮЩИЙ АВТОМАТ
Ниже представлен алгоритм программы.
пока не последняя строка mmo1 делаем: записываем содержимое каждой строки в переменную str;
st=1;
для i=первому символу строки до i равному последнему символу строки делаем:
если str[i]=x то:
увеличиваем i и запускаем функцию CheckDigit определяющую принадлежность символа содержащегося в str[i] к множеству {0,1,2,3,4,5,6,7}. Если принадлежит то переходим в b, если нет выходим из цикла и показываем ошибку;
запускам функцию NextState в которую передаётся текущее значение st и значение str[i], функция возвращает следующее значение st;
outst=outst+st;
возвращаемся к шагу 3;
если str[i]<>x то выводим ошибку;
выводим outst;
9 Описание контрольного примера
Назначение
Контрольный пример необходим для тестирования программной реализации автомата - программы «recognizing».
Исходные данные
Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата: {x0, x1, x2, x3, x4, x5, x6, x7}.
Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики. Для проверки правильности работы автомата нужно проверить его с помощью допустимых цепочек. Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символS. Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал. Выписать терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.
Для полной проверки автомата получим несколько недопустимых цепочек. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле. Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.
Результаты испытания программы.
Результаты испытаний представлены в таблице 9.1
|
Входная цепочка |
Результат работы программы |
|
x2x4x2x3x0 |
Правильная цепочка |
|
x6x0x0x5x5 |
Правильная цепочка |
|
x5x3x0 |
Правильная цепочка |
|
x2x4x3 |
Незаконченная цепочка |
|
x6x3x0 |
Незаконченная цепочка |
|
x2x4x5 |
Незаконченная цепочка |
Таблица 9.1 Результаты испытаний
Результаты испытания программы совпали с ожидаемыми, что говорит о правильности построения минимального автомата и реализации программы.
ЗАКЛЮЧЕНИЕ
В ходе данной работы было выполнено построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Автоматы, полученные двумя способами, идентичны, что говорит о правильности выполнения вычислений.
Для автоматизированной обработки входных последовательностей была реализована программа с устанавливаемым автоматом. Проверка теоретически построенных допустимых и недопустимых последовательностей показала, что программа работает верно.
СПИСОК ЛИТЕРАТУРЫ
Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» / Сост. М. А. Сенилов. – Ижевск:
Изд-во ИжГТУ, 2008. – 28 с.
ПРИЛОЖЕНИЕ A
Исходный код
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
mmo1: TMemo;
mmo2: TMemo;
btn1: TButton;
procedure btn1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
function CheckDigit(ch:char):boolean;
function NextState(sym:char; state:string):string;
implementation
{$R *.dfm}
function NextState(sym:char; state:string):string;
begin
if state='1' then
case sym of
'2':begin result:='2'; exit; end;
'6':begin result:='7'; exit; end;
'4':begin result:='4'; exit; end;
else begin result:='0'; exit; end;
end;
if state='2' then
case sym of
'4':begin result:='3'; exit; end;
else begin result:='0'; exit; end;
end;
if state='3' then
case sym of
'2':begin result:='4'; exit; end;
'5':begin result:='4'; exit; end;
else begin result:='0'; exit; end;
end;
if state='4' then
case sym of
'3':begin result:='5'; exit; end;
else begin result:='0'; exit; end;
end;
if state='5' then
case sym of
'0':begin result:='11'; exit; end;
'5':begin result:='1'; exit; end;
else begin result:='0'; exit; end;
end;
if state='6' then
case sym of
'7':begin result:='10'; exit; end;
else begin result:='0'; exit; end;
end;
if state='7' then
case sym of
'6':begin result:='6'; exit; end;
'0':begin result:='8'; exit; end;
'3':begin result:='8'; exit; end;
else begin result:='0'; exit; end;
end;
if state='8' then
case sym of
'0':begin result:='9'; exit; end;
else begin result:='0'; exit; end;
end;
if state='9' then
case sym of
'5':begin result:='10'; exit; end;
else begin result:='0'; exit; end;
end;
if state='10' then
case sym of
'5':begin result:='11'; exit; end;
else begin result:='0'; exit; end;
end;
if state='11' then result:='0';
end;
function CheckDigit(ch:char):boolean;
begin
case ch of
'0':result:=true;
'1':result:=true;
'2':result:=true;
'3':result:=true;
'4':result:=true;
'5':result:=true;
'6':result:=true;
'7':result:=true
else result:=false;
end;
end;
procedure TForm1.btn1Click(Sender: TObject);
var
i:word;
s,st,outst:string;
symbol:char;
begin
for i := 0 to Form1.mmo1.Lines.Count-1 do
s:=s+Form1.Mmo1.Lines[i];
i:=1;
st:='1';
outst:='1';
while i<=Length(s) do begin
symbol:=s[i];
inc(i);
if symbol='x' then begin
symbol:=s[i];
if CheckDigit(symbol) then begin
st:=NextState(symbol,st);
outst:=outst+' '+st;
end
else
st:='0';
end
else begin
Form1.mmo2.Lines.Add('Ошибка на символе '+ symbol);
break;
end;
inc(i);
if st='0' then begin
Form1.mmo2.Lines.Add('Ошибка на символе '+ symbol);
break;
end;
end;
////
if st='11' then begin
Form1.mmo2.Lines.Add('Правильная строка');
Form1.mmo2.Lines.Add('Состояния: '+ outst)
end
else Form1.mmo2.Lines.Add('Незаконченная строка')
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
Form1.mmo1.Lines.Clear;
Form1.mmo2.Lines.Clear;
end;
end.
ПРИЛОЖЕНИЕ Б
Контрольный пример
На рисунке Б.1 изображен пример работы программы на верных исходных данных.
Рисунок Б.1
На рисунке Б.2 изображен пример работы программы на неверных исходных данных.
Рисунок Б.2