Синтез распознающего автомата
Министерство
образования и науки РФ
ГОУ ВПО
«Ижевский государственный технический университет»
Кафедра
«Программное обеспечение»
ПОЯСНИТЕЛЬНАЯ
ЗАПИСКА
к курсовой
работе
по
дисциплине:
«Теория
языков программирования и методы трансляции»
на тему:
«Синтез
распознающего автомата»
Выполнил:
ст.гр. 4-78-11
Таишев Е.Э.
Ижевск 2012
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. Постановка задачи
2. Индивидуальное задание. Построение праволинейной
грамматики
3. Построение автоматной грамматики по праволинейной
4. Построение недетерминированного конечного автомата
5. Сведение недетерминированного конечного автомата к
детерминированному
6. Построение минимального автомата
. Построение сети Петри, моделирующей работу распознающего
автомата
. Описание программы, реализующей распознающий автомаТ
8.1
Вводная часть
8.2
Функциональное назначение
.3
Описание информации
.4
Описание логики
9 Описание контрольного примера
9.1
Назначение
9.2
Исходные данные
.3 Результаты
расчета
.4
Результаты испытания программы
ЗАКЛЮЧЕНИЕ
СПИСОК
ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ
ВВЕДЕНИЕ
Цель курсовой работы состоит в изучении способов задания языков
грамматиками, распознающими автоматами и сетями Петри, построении модели
конечного автомата, распознающего заданный язык и его программная реализация.
В наше время, конечные автоматы имеют широкое распространение в
компиляторах языков, поэтому программная реализация конечного автомата
приобретает высокое значение. Также они применяются для создания
лингвистических процессоров, для описания и обработки формальных языков.
Каждый автомат имеет конечное число входов, воспринимающих информацию,
изображаемую конечным числом символов из некоторого алфавита, и конечное число
выходов для выдачи информации.
Выходная информация автомата зависит не только от входной информации, но
и от внутреннего состояния автомата. Конечный автомат имеет конечное число
состояний.
Автоматы часто представляют сетями. Для автомата характерен
последовательный способ функционирования: автомат последовательно переходит из
состояния в состояние с заданной функцией перехода и осуществляет очередной
шаг.
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;® C1 C4 C5
B;® C6
C;® C7
F;® C8
D;® C9;® C8 E;® C9;® C8 E;® C9;® C10 S;® C11;® C10 S;® C11;® C12 C13 C14
C15;® C16 C13 C14 C15; ® C17 C18 C15.
2.
ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ
Индивидуальным задание для курсовой работы являются две таблицы (см.
табл., 1,2) и правила вывода R.
необходимо поставить в соответствие терминальным символам Ci грамматики G терминальные символы Xi грамматики G’. Для этого во вторую строку таблицы 1 записываются первые 18
символов фамилии, имени и отчества с обязательными пробелами между ними. В
третью строку необходимо занести для каждого из 18 символов строки символы из
алфавита {X0, X1,
X2, X3, X4,
X5, X6, X7} в
соответствии с таблицей 2.
Таблица 1. Индивидуальная таблица
|
Ci
|
C1
|
C2
|
C3
|
C4
|
C5
|
C6
|
C7
|
C8
|
C9
|
C10
|
C11
|
C12
|
C13
|
C14
|
C15
|
C16
|
C17
|
C18
|
|
S1
|
Т
|
А
|
И
|
Ш
|
Е
|
В
|
|
Е
|
В
|
Г
|
Е
|
Н
|
И
|
Й
|
|
Э
|
Д
|
У
|
|
Xi
|
X5
|
X1
|
X3
|
X2
|
X6
|
X2
|
X5
|
X6
|
X2
|
X4
|
X6
|
X7
|
X3
|
X0
|
X5
|
X1
|
X6
|
X7
|
Таблица 2. Таблица соответствия между буквами алфавита и терминальными
символами грамматики G’
|
А
|
Б
|
В
|
Г
|
Д
|
Е
|
Ж
|
З
|
И
|
Й
|
К
|
Л
|
М
|
Н
|
О
|
П
|
|
X1
|
X5
|
X2
|
X4
|
X6
|
X6
|
X4
|
X3
|
X3
|
X0
|
X7
|
X0
|
X3
|
X7
|
X4
|
X5
|
|
Р
|
С
|
Т
|
У
|
Ф
|
Х
|
Ц
|
Ч
|
Ш
|
Щ
|
Ь
|
Ы
|
Э
|
Ю
|
Я
|
|
|
X0
|
X4
|
X5
|
X7
|
X2
|
X5
|
X1
|
X2
|
X2
|
X0
|
X6
|
X1
|
X1
|
X3
|
X7
|
X5
|
Правила вывода для G’ получаются из правил вывода
грамматики G заменой символов Ci на соответствующие символы Xi. При этом праволинейная грамматика
приводится к следующему виду:
G’ =
<Vt’, Vn’, S’, P’>,
где
Vt’= { X0, X2, X3, X4, X5, X6, X7} - терминальный словарь,
Vn’= {S, A, B, C, D, E, F}- нетерминальный словарь,
S - начальный
символ грамматики, S Vn,- множество правил вывода, получаемых из правил
вывода R заменой символов Ci на Xi в соответствии с таблицей 1.
Получим
следующие правила вывода праволинейной грамматики G’:
1.
S® x5 x1 x3 A
2.
S® x5 x2 x6 B
3.
S® x2 C
4.
S® x5 F
5.
A® x6 D
6.
A® x2
7.
B® x6 E
8.
B® x2
9.
C® x6 E
10.C® x2
11.D® x4 S
12.D® x6
13.E® x4 S
14.E® x6
15.F® x7 x3 x0 x5
16.F® x1 x3 x0 x5
17.F® x6 x7 x5
Граф полученной грамматики представлен на рис. 1.
Рис. 1. Граф грамматики G’
3.
ПОСТРОЕНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПО ПРАВОЛИНЕЙНОЙ
Процедура перевода праволинейной грамматики в автоматную состоит из
следующих пунктов:
1. Если имеется правила вида А®w, где w - непустая терминальная цепочка, то
ввести новый нетерминальный символ В и добавить правило В®e. Затем заменить каждое из правил
вида A®w
правилом A®wB.
2. Заменить каждое правило вида A®a1...anB, для n>1, на правила:
A®a1A1
A1®a2A2
...n-1®anAn,
где: Ai, для (1
< i< (n-1)) - новые нетерминальные символы.
3. Если имеется правила вида А®B, то, во-первых, удалить правила B®B (если таковые имеются), во-вторых,
заменить их правилами вида: A®a, для всех A и a, для которых существуют правила A®B и B®a.
Применив данную процедуру перевода к полученной праволинейной грамматике
G', получим следующую автоматную грамматику:
4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА
Процедуру построения недетерминированного автомата по автоматной
грамматике:
1. Входным множеством автомата будет терминальное множество
грамматики;
2. Множеством состояний автомата будет нетерминальное множество
грамматики, а в качестве начального состояния будет выступать начальный
нетерминальный символ грамматики - S;
. По правилу Z ® e состояние Z будет допускающим;
. Для всех правил грамматики по правилу A ® xB вводим в автомате переход из состояния A в состояние B по входу x
. Чтобы получить полностью определенный автомат, вводим состояние
ошибки - Er, и во все оставшиеся клетки
записываем переход в состояние ошибки.
Результатом такого построения является недетерминированный автомат с
одним начальным состоянием. Таблицей переходов полученного автомата является
таблица 3.
Таблица 3. Недетерминированный конечный автомат
|
x0
|
x 1
|
x 2
|
x 3
|
x 4
|
x 5
|
x 6
|
x 7
|
|
|
S
|
Er
|
Er
|
C
|
Er
|
Er
|
S1F
|
Er
|
C
|
0
|
|
S1
|
Er
|
S2
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
0
|
|
S2
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
A
|
0
|
|
S3
|
Er
|
Er
|
S4
|
Er
|
Er
|
Er
|
Er
|
Er
|
0
|
|
S4
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
B
|
Er
|
0
|
|
A
|
Er
|
Er
|
Z
|
Er
|
Er
|
Er
|
D
|
Er
|
0
|
|
Z
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
1
|
|
B
|
Er
|
Er
|
Z
|
Er
|
Er
|
Er
|
E
|
Er
|
0
|
|
C
|
Er
|
Er
|
Z
|
Er
|
E
|
Er
|
E
|
Er
|
0
|
|
D
|
Er
|
Er
|
Er
|
Er
|
S
|
Er
|
Z
|
Er
|
0
|
|
E
|
Er
|
Er
|
Er
|
Er
|
S
|
Er
|
Z
|
Er
|
0
|
|
F
|
Er
|
F4
|
Er
|
Er
|
Er
|
Er
|
F7
|
F1
|
0
|
|
F1
|
Er
|
Er
|
F2
|
Er
|
Er
|
Er
|
Er
|
0
|
|
F2
|
F3
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
0
|
|
F3
|
Er
|
Er
|
Er
|
Er
|
Er
|
Z
|
Er
|
Er
|
0
|
|
F4
|
Er
|
Er
|
Er
|
F5
|
Er
|
Er
|
Er
|
Er
|
0
|
|
F5
|
F6
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
0
|
|
F6
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Z
|
Er
|
0
|
|
F7
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
F8
|
0
|
|
F8
|
Er
|
Er
|
Er
|
Er
|
Er
|
Z
|
Er
|
Er
|
0
|
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
Er
|
0
|
5.
6.
СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ
Процедура перехода от недетерминированного автомата к детерминированному:
Обозначения:
АД - детерминированный автомат
АН - недетерминированный автомат
. Пометить первую строку таблицы переходов для АД множеством начальных
состояний автомата АН.
. По данному множеству состояний B, помечающему строку таблицы переходов
автомата АД, для которой переходы еще не выполнены, вычислить те состояния АН,
которые могут быть достигнуты из B с помощью каждого входного символа и
поместить полученное множество состояний в состояние ячейки для автомата АД.
. Для каждого нового множества, порожденного на шаге 2, посмотреть:
имеется ли уже в АД строка, помеченная этим множеством, если нет, то создать
новую строку и пометить ее этим множеством. Если множество уже использовалось
как метка, то никаких действий не надо.
. Если в таблице АД есть строка, для которой еще не вычислены переходы,
то вернуться назад и применить к этой строке шаг 2. Если все переходы
вычислены, то переходим к шагу 5.
. Пометить строку как допускающее состояние АД, тогда и только тогда,
когда она содержит допускающее состояние АН, иначе пометить как отвергающее.
. Добавим состояние ошибки Er и
во всех пустых клетках запишем переход в состояние ошибки.
Получим следующий детерминированный автомат (см. табл. 4).
Таблица 4. Детерминированный автомат
|
x 0
|
x 1
|
x 2
|
x4
|
x 5
|
x 6
|
x 7
|
|
|
{S}
|
{Er}
|
{Er}
|
{C}
|
{Er}
|
{ S1F }
|
{Er}
|
{C}
|
0
|
|
{F}
|
{Er}
|
{F4}
|
{Er}
|
{Er}
|
{F1}
|
{ F7}
|
{F1 }
|
0
|
|
{C}
|
{Er}
|
{Er}
|
{Z}
|
{E}
|
{Er}
|
{ E }
|
{Er}
|
0
|
|
{S1 S3}
|
{Er}
|
{ S2}
|
{ S4}
|
{ Er }
|
{Er}
|
{ Er }
|
{Er}
|
0
|
|
{F7 }
|
{Er}
|
{ Er }
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{ F8}
|
0
|
|
{F4}
|
{Er}
|
{ F5}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
0
|
|
{F1 }
|
{Er}
|
{ F2}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
0
|
|
{Z}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
1
|
|
{E}
|
{Er}
|
{ Er }
|
{Er}
|
{ S }
|
{ Er }
|
{ Z }
|
{Er}
|
0
|
|
{S4 }
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{ B }
|
{ Er }
|
0
|
|
{S2 }
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{ A }
|
0
|
|
{F8 }
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{ Z }
|
{ Er }
|
{Er}
|
0
|
|
{F2 }
|
{Er}
|
{ F3}
|
{Er}
|
{Er}
|
{ Er }
|
{Er}
|
{Er}
|
0
|
|
{B}
|
{Er}
|
{Er}
|
{ Z }
|
{ Er }
|
{Er}
|
{ E }
|
{Er}
|
0
|
|
{A}
|
{Er}
|
{Er}
|
{ Z }
|
{ Er }
|
{Er}
|
{ D }
|
{Er}
|
0
|
|
{F3 }
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{ Z }
|
{ Er }
|
{Er}
|
0
|
|
{D}
|
{Er}
|
{ Er }
|
{Er}
|
{ S }
|
{ Er }
|
{ Z }
|
{Er}
|
0
|
|
{F5 }
|
{ F6}
|
{Er}
|
{Er}
|
{Er}
|
{ Er }
|
{Er}
|
{Er}
|
0
|
|
{F6 }
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{ Z }
|
{Er}
|
0
|
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
{Er}
|
0
|
. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА
Для получения минимального автомата воспользуемся методом разбиения.
Метод разбиения заключается в разбиении множества состояний на непересекающиеся
подмножества (блоки), такие, что неэквивалентные состояния попадают в разные
блоки.
Условия эквивалентности состояний:
1. Условие подобия: состояния S и T
должны быть либо оба допускающими, либо оба отвергающими.
2. Условие преемственности: для всех
входных символов состояния S и T должны переходить в эквивалентные состояния,
т.е. их преемники эквивалентны.
Сначала состояния разбиваются на 2 блока. Один содержит только
допускающие, другой - отвергающие. Очевидно, никакое из состояний 1-го блока не
эквивалентно ни одному состоянию второго блока, что следует из условия подобия.
Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:
. Если под действием какого-либо входного символа какая-то часть
состояний данного блока переходит в состояния из другого блока, что нарушает
условие преемственности, то необходимо разбить данный блок на части так, чтобы
не нарушалось в одном блоке условие преемственности.
2. Необходимо повторять шаг 1 до тех пор, пока дальнейшее разбиение
невозможно.
3. За один раз можно разбить только один блок.
Обозначим {S1S3} за {Y}.
.1 Делим на группы допускающих, недопускающих состояний
P0={{S, Y, S2, S4, A, B, C,
D, E, F, F1, F2, F3, F4, F5,
F6, F7, F8}, {Z}}
.2 Разбиваем по входу x2:1={{A, B, C}, {S, Y, S2,
S4, D, E, F, F1, F2, F3, F4,
F5, F6, F7, F8},{Z}}
.3 Разбиваем по входу x1:2={{A, B, C}, {F8,F5,F2,S
}, { C, F4, F7, B, A },{ Y, S2, F1,
F4},{Z}}
.4 Разбиваем по входу x7:3={A, B, C}, {F8,F5,F2,S
}, {C, F4, F7, B, A}, {F1}, {Y, S2},{Z}}
.5 Разбиваем по входу x6:4={{A, B, C}, {F8,F5,F2,S},
{ C, F4, F7, B, A }, {S2}, {E}, {F1},
{Y },{Z}}
.6 Разбиваем по входу x4:5={{A, B, C}, {F8,F5,F2,S},
{ C, F4, F7, B, A },{S2}, {E}, {S4},{D},
{F1}, {F4}, {Y},{Z}}
.7 Разбиваем по входу x5:6={{A, B, C}, {F8,F5,F2,S},
{ C, F4, F7, B, A },{S2}, {E}, {S4},{D},
{F1}, {F3},{F6} {Y},{Z}}
Дальнейшее разбиение невозможно. Перейдем к новым обозначениям:
{S} ® A
{A, B, C} ® B
{D, E} ® C
{S1, S3} ® D
{S2} ® E
{S4} ® F
{F} ® G
{F1, F4} ® H
{F2, F5} ® I
{F3, F6, F8} ® J
{F7} ® K
{Z} ® L
Таблица 6.1
|
x1
|
x 2
|
x 3
|
x 4
|
x 5
|
x 6
|
x 7
|
|
|
A
|
G
|
B
|
R
|
R
|
D
|
R
|
R
|
0
|
|
B
|
R
|
L
|
R
|
R
|
R
|
C
|
R
|
0
|
|
C
|
R
|
R
|
R
|
R
|
L
|
R
|
0
|
|
D
|
E
|
F
|
R
|
R
|
R
|
R
|
R
|
0
|
|
E
|
R
|
R
|
B
|
R
|
R
|
R
|
R
|
0
|
|
F
|
R
|
R
|
R
|
R
|
R
|
B
|
R
|
0
|
|
G
|
H
|
R
|
R
|
R
|
R
|
K
|
H
|
0
|
|
H
|
R
|
R
|
I
|
R
|
R
|
R
|
R
|
0
|
|
I
|
JR
|
R
|
R
|
R
|
R
|
R
|
R
|
0
|
|
J
|
R
|
R
|
R
|
R
|
L
|
R
|
R
|
0
|
|
K
|
R
|
R
|
R
|
R
|
R
|
R
|
J
|
0
|
|
L
|
R
|
R
|
R
|
R
|
R
|
R
|
R
|
1
|
Граф переходов минимального автомата приведен на рис.3.
Рис.
3 Граф переходов минимального автомата
.
ПОСТРОЕНИЕ СЕТИ ПЕТРИ
Для
полученной в п.2 праволинейной грамматики построим сеть Петри. Это можно
сделать, поставив в соответствие нетерминальным символам грамматики позиции
сети Петри, а терминалам - переходы сети Петри. Будем помечать позиции и
переходы соответствующими нетерминалами и терминалами. Если в правой части
имеет место конкатенация терминалов (т.е. цепочка терминалов), то в сети Петри
между переходами, помеченными терминалами, должны появиться дополнительные
позиции, которые будут помечены символами левой части правила подстановки с
верхними индексами 1,2…
При
построении остальных фрагментов соответствующих последующим правилам
подстановки, следует использовать ранее обозначенные позиции, но не переходы.
Таким образом, позиции могут иметь несколько входящих и исходящих дуг, а
переходы могут иметь в точности по одной входящей и не более чем по одной
исходящей дуге. Исходящая дуга может отсутствовать, если в правой части правила
подстановки отсутствует замыкающий нетерминал. Маркером или фишкой отмечается
позиция, соответствующая начальному символу грамматики. Построим сеть Петри
(рис.4)
Рис.
4 Сети Петри
Полученная
сеть представляет собой автоматную сеть Петри. Позиции можно трактовать как
состояния конечного автомата, а переходы - как входные символы. Для полноты
соответствия сети Петри распознающему автомату введена заключительная позиция
Z, в которую направлены дуги из всех переходов, ранее не имевших исходящих дуг.
Можно
заметить, что в этой сети имеются идентичные фрагменты, которые можно склеить.
Склеивая фрагменты с позициями S1, S3 по входному переходу X5, устраняем недетерминированность сети. Это позволит
произвести еще ряд склеек. Позиции A, B и C
склеиваются по выходным переходам X5 и X1, позиции
D, E - по входному переходу x5 и по выходному переходу X6. Функционирование сети не изменится, если склеить
идентичные фрагменты: F3,F6 и F8; F2 и F5; F1 и F4. Этот
этап соответствует минимизации числа состояний автомата. Получим эквивалентную
детерминированную сеть следующего вида (см. рис.5):
Рис. 5 Эквивалентная детерминированная сеть Петри
По полученной сети построим граф.
Введем следующие обозначения:
{S} ® A
{A, B, C} ® B
{D, E} ® C
{S1, S3} ® D
{S2} ® E
{S4} ® F
{F} ® G
{F1, F4} ® H
{F2, F5} ® I
{F3, F6, F8} ® J
{F7} ® K
{Z} ® L
Граф приведен на рис.6.
Рис.6
Граф полученной сети
Сравнив два графа (рис.3 и рис.6), можно увидеть, что они в точности
совпадают.
8.ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ РАСПОЗНАЮЩИЙ АВТОМАТ
.1 Вводная часть
Для проверки правильности построенного конечного распознавателя, написана
программа. Программа реализует работу распознающего автомата и производит
распознавание вводимых с клавиатуры цепочек. Программа написана на языке TURBO PASCAL. Для проверки работоспособности необходимо
откомпилировать файл automat.pas,
далее запустить файл automat.exe.
.2 Функциональное назначение
Программа имитирует работу конечного автомата. Программа применяется для
распознавания входных цепочек символов право-линейной грамматики.
Для функционирования программы необходима любая ЭВМ, имеющая
транслятор языка Паскаль.
Для работы программы требуются следующие устройства:
·
дисплей;
·
клавиатура.
Для работы программы необходимо:
·
объем свободной
оперативной памяти не менее 10 Kb;
При сбоях в работе устройств, программа прекращает свою работу.
Программа не предусматривает возможности продолжения работы с
определенного этапа.
8.3 Описание информации
В качестве входной информации выступают строки, вводимые с клавиатуры,
состоящие из символов исходной грамматики и являющиеся строкой для
распознавания. Информация о допустимости цепочек выводится на дисплей. Входные
данные имеют формат: хАхВхС , где А, В, С - числа от 1 до 7.
Перечень сообщений, используемых в работе программы, представлен в
таблице 6.
Таблица 6. Сообщения программы
|
Сообщение
|
Описание
|
|
Введите цепочку:
|
Приглашение к вводу цепочки.
|
|
Цепочка не допускается
|
Выводится, если введенная цепочка является недопустимой
|
|
Цепочка допускается
|
Выводится, если введенная цепочка является допустимой
|
.4 Описание логики
Логику написанной программы иллюстрирует схема программы, представленная
на рис. 7
Рис. 7 Схема программы automat.pas
9. ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА
.1 Назначение
Контрольный пример предназначен для тестирования программы automat.pas, реализующей конечный автомат.
.2 Исходные данные
Исходные данные - цепочка символов. В нее входят символы из множества:
{x1,x2,x3,x4,x5,x6,x7}.
Построим правильные цепочки:
. SÞx7x6x6AÞx7x6x6x6DÞx7x6x6x6x3
1 5 12
Получаем цепочку: x7x6x6x6x3
2. SÞx7x4x3BÞx7x4x3x6EÞx7x4x3x6x5SÞ x7x4x3x6x5x4CÞ x7x4x3x6x5x4x2
2 7 13 3 10
Получаем цепочку: x7x4x3x6x5x4x2
3. SÞx4CÞx4x6EÞx4x6x5SÞ x4x6x5x1FÞ x4x6x5x1x5x1x3
3 9 13 4 17
Получаем цепочку: x4x6x5x1x5x1x3
4. SÞx1FÞx1x1x7x4x3
4 15
Получаем цепочку: x1x1x7x4x3
5. SÞx1FÞx1x3x7x4x3
4 16
Получаем цепочку: x1x3x7x4x3
Построим не правильные цепочки:
. SÞx7x6x6AÞx7x6x6x3
1
Получаем цепочку: x7x6x6x3
2. SÞx4x6x1
Получаем цепочку: x4x6x1
3. SÞx4CÞx4x6EÞ x4x6x4
3 9
Получаем цепочку: x4x6x4
9.3 Результаты расчета
Следующие цепочки являются допустимыми т.к. после прочтения любой из них
автомат переходит в допускающее состояние:
1. x7x6x6x6x3
®3®6®10®8®13
. x7x4x3x6x5x4x2
®3®4®10®8®1®10®13
. x4x6x5x1x5x1x3
®10®8®1®11®7®9®13
. x1x1x7x4x3
®11®2®5®9®13
. x1x3x7x4x3
®11®2®5®9®13
Следующие цепочки являются не допустимыми т.к. после прочтения любой из
них автомат переходит в не допускающее состояние:
1. x7x6x6x3
®3®6®10®12
. x4x6x1
®3®4®12
. x4x6x4
®10®8®12
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
Цепочка допустима