Лабораторная работа №3 Распараллеливание вычислительного алгоритма

Лабораторная работа №1 Программная реализация распознающего автомата

Цель работы

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

Исходные данные

Для написания программы распознающего автомата используются:

-таблица кодирования символов входного алфавита, приведенная

в разделе 1 методических указаний к курсовой работе:

Таблица 1

 

S| А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Э

Ю

Я |

j | 1

7 | 5

 

-таблица (или граф) переходов детерминированного автомата,

полученная в разделе 4 методических указаний к курсовой работе.

Алгоритм работы автомата

Будем обозначать состояния автомата следующими символами:

0 - начальное состояние,

1:N - промежуточное состояние,

N+1 - заключительное состояние,

N+2 - состояние "ошибка".

Следует также назначить некоторый символ, не содержащийся во

входном алфавите, символом "конец слова" и сопоставить ему код

j = 8. С учетом зтого следует представить таблицу переходов в

следующем виде:

Таблица 2

Код состояния	Входной символ
. . .
N

 

Эту таблицу необходимо заполнить в соответствии с таблицей

переходов, полученной в курсовой работе, с учетом символа "конец

слова". Схема алгоритма работы автомата приведена на рисунке.

 

 

 

 

Порядок выполнения работы

- написать программу в соответствии с алгоритмом,

приведенным на рисунке,

- составить наборы допустимых и недопустимых слов по графу

переходов распознающего автомата,

- выполнить тестирование программы на составленных наборах

слов,

- продемострировать работу автомата преподавателю,

- распечатать текст программы и результаты тестирования,

- составить отчет по работе.

5. Содержание отчета:

- граф переходов распознающего автомата,

- текст программы,

- наборы допустимых и недопустимых слов,

- распечатки результатов тестирования программы.

Лабораторная работа №2 Минимизация числа состояний распознающего аппарата

Цель работы

Разбиение множества состояний автомата на классы эквивалентности с помощью алгоритма Мили.

Исходные данные

Таблица переходов распознающего аппарата, структура которой приведена в описании работы №1 (Табл. 2).

Основные теоретические положения

Поиск пар эквивалентных состояний по заданной таблице переходов М производится я на основе двух положений:

1) Состояния i и k явно не эквивалентны, если в таблице М существует хотя бы один столбец j такой, что (M(i,j)=N+2 и M(k,j) ¹ N+2) или (M(k,j)=N+2 и M(i,j) ¹ N+2), где N+2 - состояние “Ошибка”.

2) Состояния i и k эквивалентны, если строки i и k в таблице М одинаковы или становятся одинаковыми при замене соответствующих элементов этих строк на эквивалентные состояния.

С помощью 1-го положения производится первоначальное разбиение множества состояний на классы так, что состояния, попавшие в разные классы, явно не эквивалентны.

После этого составляется множество S0 всех пар состояний, которые не являютсяявно неэквивалентными. Затем из этого множества исключаются те пары, для которых не выполняется 2-ое положение. Это делается с помощью матрицы пар MP, строки которой соответствуют парам состояний, “подозрительных” на эквивалентность, а в столбцах указываются пары, в которые они переходят под действием входных символов. Процесс исключения пар осуществляется в несколько шагов. На первом шаге удаляются те пары, которые переходят в пары, состоящие из разных состояний и отсутствующие в первоначальном множестве пар S0, в итоге получается множество пар S1. На втором шаге из S1 удаляются те пары, которые переходят в пары, состоящие из разных состояний и отсутствующие в S1, получается множество пар S2 и т.д. Удаление пар заканчивается на k-том шаге, когда множество SK совпадает с множеством, полученным на предыдущем шаге.

Описание алгоритма

{Задана таблица переходов M[0..N],[0..8]}

{Строится матрица F[1..N,1..N] первоначального}

{разбиения на классы: F[i,k]=i, если}

{состояние k включается в тот же класс, что и i}

{Начальное состояние O образует отдельный класс}

{В векторе G фиксируются те состояния, которые}

{Уже включены в какой-то класс.}

G(i):=0 для i=1..N;

Цикл i:=1..N

IF G(i)=0 THEN

BEGIN F(i,i):=i;

Цикл K=i+1..N

IF G(K)=0 THEN BEGIN

j:=-1;

REPEAT j:=j+1

UNTIL (j=8

или M(i,j)=N+2 и M(k,j)¹N+2

или M(k,j)=N+2 и M(i,j)¹N+2);

IF j=8 THEN BEGIN

F(j,k):=i; G(k):=1 END

ELSE F(i,k):=0

END(*G(k)*)

КЦ(*K*)

END

ELSE F(i,s):=0 для S=i..N

КЦ(*i*)

{Строится матрица пар MP[1..NMP,1..21],}

{во 2-ом столбце указывается 1-ый элемент}

{пары, в 3-ем столбце - 2-ой элемент,}

{в столбцах 4+2*k и 5+2*k -элементы}

{пар, в которые переходит данная пара под}

{действием входного символа k;}

{1-ый столбец матрицы MP используется}

{в дальнейшем для удаления пары.}

{В вектор GF[1..N] переносятся номера}

{состояний, включенных в один класс с состоянием i.}

t:=1

Цикл i=1..N

GF(S):=0 для S=1..N;

j:=0;

Цикл l=j..2 шаг -1

Цикл m=j-1..1 шаг -1

MP(t,1):=0;

MP(t,2):=GF(m);

MP(t,3):=GF(l);

Цикл k=0..8

MP(t,4+2*k):=M(G(m),k);

MP(t,5+2*k):=M(G(l),k);

КЦ(*k*); t:=t+1;

КЦ(*m*)

КЦ(*l*);

КЦ(*i*);

NMP:=t-1; {число строк в матрице MP}

{В 1-ом столбце матрицы MP отмечаются те строки, которые}

{соответствуют парам, удаляемым из классов эквивалентности}

{Удаление прекращается, когда на очередном шаге не отмечена}

{ни одна новая строка в матрице MP}

SMP:=0;

REPEAT SMPS:=SMP; SMP:=0

Цикл i=1..NMP

k:=-1;

REPEAT k:=k+1;

IF (MP(i,4+2*k)№MP(i,5+2*k))

THEN BEGIN PR:=1;

t:=0;

REPEAT t:=t+1;

IF MP(t,1)=0 then

IF (((MP(i,4+2*k)=MP(t,2)) или

(MP(i,4+2*k)=MP(t,3))) и

((MP(i,5+2*k)=MP(t,2)) или

(MP(i,5+2*k)=MP(t,3))))

THEN PR:=0

UNTIL (t=NMP или PR=0);

MP(i,1):=PR

END

UNTIL(k=8 или MP(i,1)=1);

SMP:=SMP+MP(i,1)

(*КЦ(i)*)

UNTIL(SMP=SMPS)

{Вывод пар эквивалентности состояний}

Цикл i=1..NMP

IF (MP(i,1)=0) THEN

Вывод(MP(i,2), MP(i,3))

(*КЦ(i)*)

После вывода пар эквивалентности состояний строится матрица переходов минимального автомата. Эта процедура может быть включена в программу (по желанию студента).

5. Порядок выполнения работы:

· написать программу, реализующую приведенный алгоритм;

· для заданной таблицы переходов M[0..N,0..8] (см. работу №1) решить задачу поиска эквивалентных пар;

· Построить таблицу и граф переходов минимального автомата (вручную или автоматически);

· убедиться в эквивалентности исходного и минимального автоматов путем тестирования минимального автомата на тех же входных словах, что и в работе №1.

6. Содержание отчета:

· граф и таблица переходов исходного автомата;

· текст программы разбиения состояний на эквивалентные пары;

· распечатка результатов работы программы;

· граф и таблица переходов минимального автомата;

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

Лабораторная работа №3 Распараллеливание вычислительного алгоритма.

Цель работы

Построение матрицы независимости операторов и сети Петри по заданному информационно-логическому графу.