Синтез распознающего автомата
Изучение способов задания языков грамматиками, распознающими автоматами и сетями Петри. Синтез и программная реализация конечного автомата, распознающего заданный язык. Переходы недетерминированного полностью определённого автомата, построение графика.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 27.06.2013 |
| Размер файла | 912,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное учреждение высшего профессионального образования
«Ижевский государственный технический университет им. М.Т.Калашникова»
Кафедра АСОИУ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
по дисциплине «Математическая лингвистика»
на тему «Синтез распознающего автомата»
Выполнил:
студент гр. Б04-782-1 Н.А.Пономарев
Руководитель:
ассистент каф.АСОИУ Д.Р.Касимов
Ижевск 2013
ВВЕДЕНИЕ
Проектирование распознающего автомата и его программная реализация необходимы при построении узлов цифровых вычислительных машин, при создании компиляторов, лингвистических процессоров и лексических анализаторов в трансляторах.
Конечный автомат - это абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Целью курсовой работы является изучение способов задания языков грамматиками, распознающими автоматами и сетями Петри, синтез и программная реализация конечного автомата, распознающего заданный язык.
1. ПОСТАНОВКА ЗАДАЧИ
Построить модель распознающего автомата на основе индивидуального задания.
Для этого необходимо на основе формальной грамматики получить праволинейную грамматику, построить ее граф. По праволинейной грамматики построить автоматную. Затем построить недетерминированный распознающий автомат, задать таблицу переходов для него и изобразить граф переходов. Перейти от недетерминированного к полностью определенному детерминированному автомату. Задать таблицу переходов и изобразить граф переходов для полученного автомата. Минимизировать этот автомат. Задать таблицу переходов и граф переходов для минимального автомата.
Получить граф переходов минимального автомата по праволинейной грамматике используя сети Петри. Сравнить полученную автоматную сеть с графом минимального автомата.
Входными данными для автомата является цепочка из терминальных символов. На выходе автомата появляется состояние, отвергающее или допускающее входную цепочку.
Задана формальная грамматика
G=<Vt, Vn, S, R>, где
Vt = {C1, C2,…, C18} - терминальный словарь,
Vn = {S, A, B, C, D, E, F} - нетерминальный словарь,
S - начальный символ грамматики, SVn,
P - множество правил вывода
Правила вывода имеют следующий вид:
Sc1 c2 c3 A; Sc1 c4 c5 B; Sc6 C; Sc7 F;
Ac8 D; Ac9; Bc8 E; Bc9; Cc8E; Cc9;
Dc10 S; Dc11; Ec10 S; Ec11;
Fc12 c13 c14 c15; Fc16 c13 c14 c15; Fc17 c18 c15.
2. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ
Индивидуальное задание формируется посредством занесения во вторую строчку таблицы 1.1 имени фамилии и отчества студента.
|
ci |
c1 |
c2 |
c3 |
c4 |
c5 |
c6 |
c7 |
c8 |
c9 |
c10 |
c11 |
c12 |
c13 |
c14 |
c15 |
c16 |
c17 |
c18 |
|
|
si |
П |
О |
Н |
О |
М |
А |
Р |
Е |
В |
Н |
И |
К |
И |
Т |
А |
А |
|||
|
xi |
X5 |
X4 |
X7 |
X4 |
X3 |
X1 |
X0 |
X6 |
X2 |
X5 |
X7 |
X0 |
X7 |
X0 |
X5 |
X1 |
X5 |
X1 |
Таблица 1.1. Формирование варианта задания
Третья строчка заполняется с помощью таблицы 1.2.
|
А |
Б |
В |
Г |
Д |
Е |
Ж |
З |
И |
Й |
К |
Л |
М |
Н |
О |
П |
|
|
x1 |
x5 |
x2 |
x4 |
x6 |
x6 |
x4 |
x3 |
x3 |
x0 |
x7 |
x0 |
x3 |
x7 |
x4 |
x5 |
|
|
P |
С |
Т |
У |
Ф |
Х |
Ц |
Ч |
Ш |
Щ |
Ь |
Ы |
Э |
Ю |
Я |
_ |
|
|
x0 |
x4 |
x5 |
x7 |
x2 |
x5 |
x1 |
x2 |
x2 |
x0 |
x6 |
x1 |
x1 |
x3 |
x7 |
x5 |
Таблица 1.2. Соответствия
Заданная грамматика, являющаяся праволинейной, приводится к виду
G'=<V't, V'n, S, R'>, где V't={x0, …, x7} - новый терминальный словарь;
R' - множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V't в соответствии с таблицей 1.1. В моем варианте они имеют вид:
Sx5 x4 x7 A | x5 x4 x3 B | x1 C | x0 F;
Ax6 D | x2;
Bx6 E | x2;
Cx6 E | x;
Dx5 S | x7;
Ex5 S | x7;
Fx0 x7 x0 x5 | x1 x7 x0 x5 | x5 x1 x5.
3. ПОСТРОЕНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПО ПРАВОЛИНЕЙНОЙ
Для получения автоматной грамматики, необходимо заменить правила, у которых в правой части перед нетерминальным символом стоит более чем один терминальный, несколькими правилами.
Sx5 S1; S1x4 S2; S2x7 A;
Sx5 S3; S3x4 S4; S4x3 B;
Sx1 C;
Sx0 F;
Ax6 D; Ax2 A1; A1;
Bx6 E; Bx2 B1; B1;
Cx6 E; Cx2 C1; C1;
Dx5 S; Dx7 D1; D1;
Ex5 S; Ex7 E1; E1;
Fx0 F1; F1x7 F2; F2x0 F3; F3x5 F4; F4;
Fx1 F5; F5x7 F6; F6x0 F7; F7x5 F8; F8;
Fx5 F9; F9x1 F10; F10x5 F11; F11;
4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГ АВТОМАТА
Построим на основе грамматики G'' конечный автомат. При этом нетерминальным символам грамматики V''n поставим в соответствие состояния автомата (оставим для них те же обозначения). Начальному нетерминалу S поставим в соответствие начальное состояние автомата S. Правилам вывода поставим в соответствие переходы автомата. В результате получим таблицу 4.1 - таблицу переходов недетерминированного частичного автомата
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|||
|
S |
F |
C |
S1,S3 |
0 |
||||||
|
S1 |
S2 |
0 |
||||||||
|
S2 |
A |
0 |
||||||||
|
S3 |
S4 |
0 |
||||||||
|
S4 |
B |
0 |
||||||||
|
A |
A1 |
D |
0 |
|||||||
|
A1 |
1 |
|||||||||
|
B |
B1 |
E |
0 |
|||||||
|
B1 |
1 |
|||||||||
|
C |
C1 |
E |
0 |
|||||||
|
C1 |
1 |
|||||||||
|
D |
S |
D1 |
0 |
|||||||
|
D1 |
1 |
|||||||||
|
E |
S |
E1 |
0 |
|||||||
|
E1 |
1 |
|||||||||
|
F |
F1 |
F5 |
F9 |
0 |
||||||
|
F1 |
F2 |
0 |
||||||||
|
F2 |
F3 |
0 |
||||||||
|
F3 |
F4 |
0 |
||||||||
|
F4 |
1 |
|||||||||
|
F5 |
F6 |
0 |
||||||||
|
F6 |
F7 |
0 |
||||||||
|
F7 |
F8 |
0 |
||||||||
|
F8 |
1 |
|||||||||
|
F9 |
F10 |
0 |
||||||||
|
F10 |
F11 |
0 |
||||||||
|
F11 |
1 |
Таблица 4.1 Переходы недетерминированного частичного автомата
Полученный автомат является не полностью определенным (частичным), поскольку в таблице переходов (Таблица 4.1) есть незаполненные клетки, и, кроме того, недетерминированным, поскольку в той же таблице есть клетки, содержащие пары состояний.
Чтобы получить полностью определенный автомат, следует ввести дополнительное состояние Er (ошибка). Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. Таблица 4.2).
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|||
|
S |
F |
C |
Er |
Er |
Er |
S1,S3 |
Er |
Er |
0 |
|
|
S1 |
Er |
Er |
Er |
Er |
S2 |
Er |
Er |
Er |
0 |
|
|
S2 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
A |
0 |
|
|
S3 |
Er |
Er |
Er |
Er |
S4 |
Er |
Er |
Er |
0 |
|
|
S4 |
Er |
Er |
Er |
B |
Er |
Er |
Er |
Er |
0 |
|
|
A |
Er |
Er |
A1 |
Er |
Er |
Er |
D |
Er |
0 |
|
|
A1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
B |
Er |
Er |
B1 |
Er |
Er |
Er |
E |
Er |
0 |
|
|
B1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
C |
Er |
Er |
C1 |
Er |
Er |
Er |
E |
Er |
0 |
|
|
C1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
D |
Er |
Er |
Er |
Er |
Er |
S |
Er |
D1 |
0 |
|
|
D1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
E |
Er |
Er |
Er |
Er |
Er |
S |
Er |
E1 |
0 |
|
|
E1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
F |
F1 |
F5 |
Er |
Er |
Er |
F9 |
Er |
Er |
0 |
|
|
F1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
F2 |
0 |
|
|
F2 |
F3 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
F3 |
Er |
Er |
Er |
Er |
Er |
F4 |
Er |
Er |
0 |
|
|
F4 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
F5 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
F6 |
0 |
|
|
F6 |
F7 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
F7 |
Er |
Er |
Er |
Er |
Er |
F8 |
Er |
Er |
0 |
|
|
F8 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
F9 |
Er |
F10 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
F10 |
Er |
Er |
Er |
Er |
Er |
F11 |
Er |
Er |
0 |
|
|
F11 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
Таблица 4.2 Переходы недетерминированного полностью определённого автомата
Далее построим граф переходов (Рисунок 5.1), при этом в неё опустим состояния исходящие из не допускающих состояний и ведущие в состояние Er (ошибка).
Рисунок 4.1. Граф переходов недетерминированного автомата
5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ
синтез автомат переход язык
Процедура построения детерминированного автомата Ад, эквивалентного недетерминированному автомату Ан, задается следующими шагами:
Пометить первую строку таблицы переходов для Ад множеством начальных состояний автомата Ан. Применить к этому множеству шаг 2.
По данному множеству состояний В, помечающему строку таблицы переходов автомата Ад, для которой переходы еще не вычислены, вычислить те состояния автомата Ан, которые могут быть достигнуты из В с помощью каждого входного символа х, и поместить полученные множества состояний в соответствующие ячейки таблицы для автомата Ад. Символически это выражается так: если - функция недетерминированных переходов, то функция детерминированных перехода ' задается формулой '(B, x) = {S | S (T, x), Т В}
Для каждого нового множества, порожденного переходами на шаге 2, посмотреть, имеется ли уже в Ад строка, помеченная этим множеством. Если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, никаких действий не требуется.
Если в таблице автомата Ад есть строка, для которой еще не вычислены переходы, вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, перейти к шагу 5.
Пометить строку как допускающее состояние автомата Ад тогда и только тогда, когда она содержит допускающее состояние недетерминированного автомата. В противном случае пометить как отвергающее состояние.
Описанная процедура гарантирует, что детерминированный автомат не содержит недостижимых состояний.
С помощью этой процедуру переходим к эквивалентному детерминированному автомату (Таблица 5.1) В нашем случае были объединены состояния S1, S2 и состояния S2, S4. Перейдем к более простым обозначениям состояний:
{S}Y;{S1,S3}Y1;{S2,S4}Y2;
{A}Y3;{A1}Y4;{B}Y5;{B1}Y6;
{C}Y7;{C1}Y8;{D}Y9;{D1}Y10;
{E}Y11;{E1}Y12;{F}Y13;{F1}Y14;
{F2}Y15;{F3}Y16;{F4}Y17;{F5}Y18;
{F6}Y19;{F7}Y20;{F8}Y21;{F9}Y22;
{F10}Y23; {F11}Y24;{Er}Er.
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|||
|
{Y} |
{Y13} |
{Y7} |
{Er} |
{Er} |
{Er} |
{Y1} |
{Er} |
{Er} |
0 |
|
|
{Y1} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y2} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{Y2} |
{Er} |
{Er} |
{Er} |
{Y5} |
{Er} |
{Er} |
{Er} |
{Y3} |
0 |
|
|
{Y3} |
{Er} |
{Er} |
{Y4} |
{Er} |
{Er} |
{Er} |
{Y9} |
{Er} |
0 |
|
|
{Y4} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Y5} |
{Er| |
{Er} |
{Y6} |
{Er} |
{Er} |
{Er} |
{Y11} |
{Er} |
0 |
|
|
{Y6} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Y7} |
{Er} |
{Er} |
{Y8} |
{Er} |
{Er} |
{Er} |
{Y11} |
{Er} |
0 |
|
|
{Y8} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Y9} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y} |
{Er} |
{Y10} |
0 |
|
|
{Y10} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Y11} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y} |
{Er} |
{Y12} |
0 |
|
|
{Y12} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Y13} |
{Y14} |
{Y18} |
{Er} |
{Er} |
{Er} |
{Y22} |
{Er} |
{Er} |
0 |
|
|
{Y14} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y15} |
0 |
|
|
{Y15} |
{Y16} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{Y16} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y17} |
{Er} |
{Er} |
0 |
|
|
{Y17} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Y18} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y19} |
0 |
|
|
{Y19} |
{Y20} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{Y20} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y21} |
{Er} |
{Er} |
0 |
|
|
{Y21} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Y22} |
{Er} |
{Y23} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{Y23} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Y24} |
{Er} |
{Er} |
0 |
|
|
{Y24} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
Таблица 5.1 Переходы детерминированного автомата
Построим граф автомата(Рисунок 5.1) по таблице 5.1.
Рисунок 5.1. Граф детерминированного автомата
6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА
Произвольный конечный автомат можно превратить в эквивалентный ему минимальный, выбрасывая недостижимые и объединяя эквивалентные состояния. Разбиение состояний на классы эквивалентности можно осуществить с помощью метода разбиения.
Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества или блоки, такие, что неэквивалентные состояния попадают в разные блоки.
Начальное разбиение P0 заключается в разбиении всего множества состояний на подмножества допустимых и недопустимых состояний:
P0=({Y, Y1, Y2, Y3, Y5, Y7, Y9, Y11, Y13, Y14, Y15, Y16, Y18, Y19, Y20, Y22, Y23, Er}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Разобьем блок 1 по входу x2:
P1=({Y, Y1, Y2, Y9, Y11, Y13, Y14, Y15, Y16, Y18, Y19, Y20, Y22, Y23, Er},{Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Разобьем блок 1 по входу x3:
P2=({Y, Y1, Y9, Y11, Y13, Y14, Y15, Y16, Y18, Y19, Y20, Y22, Y23, Er},{Y2},{Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Разобьем блок 1 по входу x4:
P3=({Y, Y9, Y11, Y13, Y14, Y15, Y16, Y18, Y19, Y20, Y22, Y23, Er},{Y1},{Y2},{Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Разобьем блок 1 по входу x5:
P4=({Y, Y13, Y14, Y15, Y18, Y19, Y22, Er},{Y9, Y11},{Y},{Y16,Y20,Y23},{Y1},{Y2},{Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Разобьем блок 1 по входу x0:
P5=({Y, Y13, Y14, Y18, Er},{Y15,Y19 },{Y9, Y11}{Y},{Y16,Y20,Y23},{Y1},{Y2},{Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Разобьем блок 1 по входу x7:
P6=({ Y13, Er},{Y14, Y18},{Y15,Y19 },{Y9, Y11},{Y},{Y16,Y20,Y23},{Y1},{Y2},{Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Разобьем блок 1 по входу x1:
P7=({Er},{Y13},{Y22},{Y14, Y18},{Y15,Y19 },{Y9, Y11},{Y},{Y16,Y20,Y23},{Y1},{Y2},{Y3, Y5, Y7}, {Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24})
Множество Р7 не допускает дальнейшего разбиения ни по одному входу, оно содержит подмножества (блоки) эквивалентных состояний, которые и являются состояниями минимального автомата.
Введем обозначения для этих подмножеств - состояний минимального автомата (Таблица 6.1).
|
Блок эквивалентных состояний |
Состояние минимального автомата |
|
|
{Y} |
1 |
|
|
{Y1} |
2 |
|
|
{Y2} |
3 |
|
|
{Y3, Y5, Y7} |
4 |
|
|
{Y9, Y11} |
5 |
|
|
{Y13} |
6 |
|
|
{Y14, Y18} |
7 |
|
|
{Y15, Y19} |
8 |
|
|
{Y16, Y20, Y23} |
9 |
|
|
{Y22} |
10 |
|
|
{Y4, Y6, Y8, Y10, Y12, Y17, Y21, Y24} |
11 |
|
|
{Er} |
Er |
Таблица 6.1. Состояния минимального автомата
Далее формируем таблицу переходов минимального автомата(Таблица 6.2).
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
0 |
||
|
1 |
6 |
4 |
Er |
Er |
Er |
2 |
Er |
Er |
0 |
|
|
2 |
Er |
Er |
Er |
Er |
3 |
Er |
Er |
Er |
0 |
|
|
3 |
Er |
Er |
Er |
4 |
Er |
Er |
Er |
4 |
0 |
|
|
4 |
Er |
Er |
11 |
Er |
Er |
Er |
5 |
Er |
0 |
|
|
5 |
Er |
Er |
Er |
Er |
Er |
1 |
Er |
11 |
0 |
|
|
6 |
7 |
7 |
Er |
Er |
Er |
10 |
Er |
Er |
0 |
|
|
7 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
8 |
0 |
|
|
8 |
9 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
9 |
Er |
Er |
Er |
Er |
Er |
11 |
Er |
Er |
0 |
|
|
10 |
Er |
9 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
11 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
Таблица 6.2. Таблица переходов минимального автомата
Строим граф переходов минимального автомата(Рисунок 6.1) . Чтобы не загромождать рисунок, не изображено состояние Er, а также дуги, ведущие в него из других состояний.
Рисунок 6.1 Граф минимального автомата
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. Недетерминированная сеть Петри.
Источником недетерминированности, очевидно, могут являться лишь позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами. В данном случае к таким позициям следует отнести лишь позицию (S1, S3). Способ устранения недетерминированности виден из рисунка 7.3.
Рисунок 7.3. Детерминированная сеть Петри
Можно увидеть соответствие графа переходов минимального автомата и сети Петри, показав на сети Петри обозначение состояний минимального автомата(Рисунок 7.4)
Рисунок 7.4 Сеть Петри с состояниями минимального автомата.
8. ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА
Назначение
Контрольный пример необходим для тестирования программной реализации автомата - программы «recognizing».
Исходные данные
Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата: {x0, x1, x2, x3, x4, x5, x6, x7}.
Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики. Для проверки правильности работы автомата нужно проверить его с помощью допустимых цепочек. Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символS. Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал. Выписать терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.
Для полной проверки автомата получим несколько недопустимых цепочек. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле. Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.
Результаты испытания программы.
Результаты испытаний представлены в таблице 9.1
|
Номер |
Входная цепочка |
Результат работы программы |
|
|
1 |
x5x4x7x2 |
Правильная цепочка |
|
|
2 |
x5x4x7x6x7 |
Правильная цепочка |
|
|
3 |
x1x6x5x0x5x1x5 |
Правильная цепочка |
|
|
6 |
x0x0x7 |
Незаконченная цепочка |
|
|
7 |
x1x6x5 |
Незаконченная цепочка |
|
|
8 |
x5x4x3 |
Незаконченная цепочка |
Таблица 9.1 Результаты испытаний
Результаты испытания программы совпали с ожидаемыми, что говорит о правильности построения минимального автомата и реализации программы.
ЗАКЛЮЧЕНИЕ
В ходе данной работы было выполнено построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Автоматы, полученные двумя способами, идентичны, что говорит о правильности выполнения вычислений.
Для автоматизированной обработки входных последовательностей была реализована программа с устанавливаемым автоматом. Проверка теоретически построенных допустимых и недопустимых последовательностей показала, что программа работает верно.
СПИСОК ЛИТЕРАТУРЫ
Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» / Сост. М. А. Сенилов. - Ижевск:
Изд-во ИжГТУ, 2008. - 28 с.
ПРИЛОЖЕНИЕ 1
Исходный код
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
'0':begin result:='6'; exit; end;
'1':begin result:='4'; exit; end;
'5':begin result:='2'; 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
'3':begin result:='4'; exit; end;
'7':begin result:='4'; exit; end;
else begin result:='0'; exit; end;
end;
if state='4' then
case sym of
'2':begin result:='11'; exit; end;
'6':begin result:='5'; exit; end;
else begin result:='0'; exit; end;
end;
if state='5' then
case sym of
'5':begin result:='1'; exit; end;
'7':begin result:='11'; exit; end;
else begin result:='0'; exit; end;
end;
if state='6' then
case sym of
'0':begin result:='7'; exit; end;
'1':begin result:='7'; exit; end;
'5':begin result:='10'; exit; end;
else begin result:='0'; exit; end;
end;
if state='7' then
case sym of
'7':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:='11'; exit; end;
else begin result:='0'; exit; end;
end;
if state='10' then
case sym of
'1':begin result:='9'; exit; end;
else begin result:='0'; exit; end;
end;
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,st1,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 begin
Form1.mmo2.Lines.Add('Ошибка на символе '+ symbol);
break;
end;
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 изображен пример работы программы на верных исходных данных.
Размещено на Allbest.ru
Подобные документы
Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем.
дипломная работа [1,8 M], добавлен 18.08.2013Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа.
курсовая работа [615,1 K], добавлен 19.06.2012Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.
курсовая работа [903,9 K], добавлен 14.07.2012Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Устройство управления и синхронизации в структуре микропроцессора. Порядок синтеза конечного автомата (КА) для устройства управления ЭВМ. Алгоритм функционирования КА, заданный с помощью графа, функции переходов. Состояние триггеров в микросхеме.
методичка [1019,0 K], добавлен 28.04.2009Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.
курсовая работа [997,7 K], добавлен 28.03.2011Важный частный случай недетерминированного конечного автомата. Проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Составление формальной грамматики, блок-схемы и программы, моделирующей работу конечного автомата.
курсовая работа [210,8 K], добавлен 05.12.2013Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012
