ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА

ТЕМА, ЦЕЛЬ И СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ

 

Тема курсовой работы: Синтез распознающего автомата.

Цель курсовой работы состоит в изучении способов задания языков грамматиками, распознающими автоматами и сетями Петри, построении модели конечного автомата, распознающего заданный язык, и его программной реализации.

Содержание и основные этапы работы:

1) построение праволинейной грамматики;

2) построение автоматной грамматики по праволинейной;

3) построение недетерминированного конечного автомата;

4) сведение недетерминированного конечного автомата к детерминированному;

5) построение минимального автомата;

6) выполнение этапов 2-5 с использованием аппарата сетей Петри;

7) программная реализация автомата.

 

ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ

 

Исходными данными для курсовой работы являются две таблицы – табл. 1 и табл. 2 – и правила вывода R, приведенные ниже.

В табл. 1 первоначально записана лишь первая строка, содержащая перечисление 18 символов сi. Во вторую строку si записываются первые 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

si

Б

Е

Р

Е

С

Н

Е

В

_

В

И

К

Т

О

Р

_

В

Я

xi

x5

x6

x0

x6

x4

x7

x6

x2

x5

x2

x3

x7

x5

x4

x0

x5

x2

x7

 

Таблица 2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах контингента студентов.

Затем буквы были сформированы в восемь групп с таким расчетом, чтобы появление каждого из символов x0 – x7 было равновероятным.

                                                                                                                     Таблица 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

 

Наконец, задана формальная грамматика: G=<Vt, Vn, S, R>, где Vt={c1, c2, c3, … , c18} – терминальный словарь; Vn={S, A, B, C, D, E, F} – нетерминальный словарь; SÎVn – начальный символ грамматики; R – множество правил вывода, которые имеют следующий вид:

S®c1 c2 c3 A; S®c1 c4 c5 B; S®c6 C; S®c7 F;

A®c8 D; A®c9; B®c8 E; B®c9; C®c8E; C®c9;

D®c10 S; D®c11; E®c10 S; E®c11;

F®c12 c13 c14 c15; F®c16 c13 c14 c15; F®c17 c18 c15.

 

Эта грамматика, являющаяся праволинейной, приводится к виду

G'=<V't, V'n, S, R'>, где V't={x0, …, x7} – новый терминальный словарь;

R' – множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V't в соответствии с таблицей 1. В данном примере они имеют вид:

S®x5 x6 x0 A | x5 x6 x4 B | x7 C | x6 F;

A®x2 D | x5;

B®x2 E | x5;

C®x2 E | x5;

D®x2 S | x3;

E®x2 S | x3;

F®x7 x5 x4 x0 | x5 x5 x4 x0 | x2 x7 x0.

 

Здесь “|” – металингвистический символ (связка), читаемый как "ИЛИ".

Примеры цепочек, принадлежащих языку L(G'), порождаемому грамматикой G': x5 x6 x0 x5, x7 x2 x3, x6 x7 x5 x4 x0. Напротив, цепочки x2 x7 x0 x2 x7, x6 x5 x2 x5 x6 не принадлежат L(G'), так как они не выводимы в грамматике G'.

Грамматика G', порождаемая из заданной грамматики G, является индивидуальным заданием студента.

Примечание. Мощность |V't| словаря V't (число символов в нем) в рассмотренном случае равна 7: словарь не содержит символа x1.

 

ПЕРЕХОД ОТ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ К АВТОМАТНОЙ

 

Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в модифицированную автоматную G''=< V'_t, V''_n, S, R''>. Для рассматриваемого примера, который будет сквозным в данных указаниях, получим множество R'' правил вывода:

S®x5 S1; S1®x6 S2; S2®x0 A;

S®x5 S3; S3®x6 S4; S4®x4 B;

S®x7 C;

S®x6 F;

A®x2 D; A®x5 A1; A1®e;

B®x2 E; B®x5 B1; B1®e;

C®x2 E; C®x5 C1; C1®e;

D®x2 S; D®x3D1; D1®e;

E®x2 S; E®x3 E1; E1®e;

F®x7 F1; F1®x5 F2; F2®x4 F3; F3®x0 F4; F4®e;

F®x5 F5; F5®x5 F6; F5®x4 F7; F7®x0 F8; F8®e;

F®x2 F9; F9®x7 F10; F10®x0 F11; F11®e.

Таким образом, нетерминальный словарь теперь имеет вид V''_n = {S, S1, S2, S3, S4, A, A1, B, B1, C, C1, D, D1, E, E1, F, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11} и его мощность |V''_n| равна 27.

 

ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА

 

Построим на основе грамматики G'' конечный автомат. При этом нетерминальным символам грамматики V''_n поставим в соответствие состояния автомата (оставим для них те же обозначения). Начальному нетерминалу S поставим в соответствие начальное состояние автомата S. Правилам вывода поставим в соответствие переходы автомата.

В результате получим таблицу 3 – таблицу переходов недетерминированного конечного автомата, соответствующего рассматриваемому примеру.

                                                                                                                     Таблица 3

Таблица переходов недетерминированного частичного автомата

	x0	x2	x3	x4	x5	x6	x7
S					S1,S3	F	C	0
S1						S2		0
S2	A							0
S3						S4		0
S4				B				0
A		D			A1			0
A1								1
B		E			B1			0
B1								1
C		E			C1			0
C1								1
D		S	D1					0
D1								1
E		S	E1					0
E1								1
F		F9			F5		F1	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

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

Чтобы получить полностью определенный автомат, следует ввести дополнительное состояние Er (ошибка). Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. табл. 4).

                                                                                                                     Таблица 4

Таблица переходов недетерминированного полностью определенного автомата

	x0	x2	x3	x4	x5	x6	x7
S	Er	Er	Er	Er	S1,S3	F	C	0
S1	Er	Er	Er	Er	Er	S2	Er	0
S2	A	Er	Er	Er	Er	Er	Er	0
S3	Er	Er	Er	Er	Er	S4	Er	0
S4	Er	Er	Er	B	Er	Er	Er	0
A	Er	D	Er	Er	A1	Er	Er	0
A1	Er	Er	Er	Er	Er	Er	Er	1
B	Er	E	Er	Er	B1	Er	Er	0
B1	Er	Er	Er	Er	Er	Er	Er	1
C	Er	E	Er	Er	C1	Er	Er	0
C1	Er	Er	Er	Er	Er	Er	Er	1
D	Er	S	D1	Er	Er	Er	Er	0
D1	Er	Er	Er	Er	Er	Er	Er	1
E	Er	S	E1	Er	Er	Er	Er	0
E1	Er	Er	Er	Er	Er	Er	Er	1
F	Er	F9	Er	Er	F5	Er	F1	0
F1	Er	Er	Er	Er	F2	Er	Er	0
F2	Er	Er	Er	F3	Er	Er	Er	0
F3	F4	Er	Er	Er	Er	Er	Er	0
F4	Er	Er	Er	Er	Er	Er	Er	1
F5	Er	Er	Er	Er	F6	Er	Er	0
F6	Er	Er	Er	F7	Er	Er	Er	0
F7	F8	Er	Er	Er	Er	Er	Er	0
F8	Er	Er	Er	Er	Er	Er	Er	1
F9	Er	Er	Er	Er	Er	Er	F10	0
F10	F11	Er	Er	Er	Er	Er	Er	0
F11	Er	Er	Er	Er	Er	Er	Er	1
Er	Er	Er	Er	Er	Er	Er	Er	0

 

Граф переходов автомата, построенный по таблице 4, показан на рис. 1.

 

 

Рис. 1. Граф переходов исходного (недетерминированного) автомата

 

Примечание. Для того чтобы не затемнять картину, на рисунке опущены дуги, исходящие из недопускающих состояний и ведущие в состояние Er (ошибка). Так, например, опущена дуга, ведущая из состояния S в состояние Er, которая должна быть помечена дизъюнкцией входных символов x0Úx2Úx3Úx4.

Все дуги, ведущие из допускающих состояний в состояние Er, должны быть помечены дизъюнкцией x0Úx2Úx3Úx4Úx5Úx6Úx7.

Нетрудно убедиться, что построенный автомат допускает все те и только те цепочки символов, которые принадлежат языку L(G'), порождаемому грамматикой G'.