Файл: Методические указания к решению задач по дисциплине Теория автоматов и алгоритмические языки.pdf

15
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
1 1
1 1
(
)
m
i
j
k
k
m
c
c
C
c
c
c
















,
(5) где так называемые немые индексы i и j последовательно пробегают ряд натуральных чисел
Упражнение 2.8. Для номеров ,i j

показать, что можно создать такой словарь
( )
L
Dc
языка
2
: ,
s
t
L
X
x
x
s t




, в котором формула для вычисления номера слова
i
i
j
j
x
x
c

из матрицы (5) имеет вид:
( )
( )
((
2) (
1)) /2

16
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
из вершины
i
v
V

и входит в вершину
j
v
V

. Для наглядного представления орграфа используют его рисунок в виде диаграммы орграфа, на которой вершины изображаются, как правило, кружочками, помеченными соответствующими словами языка V , и дуги – стрелками, связывающими соответствующие вершины. В упрощѐнной диаграмме орграфа вершины-кружочки остаются пустыми.
Рис.1
Рис.2
Пример 3.1. На рис. 1 (рис. 2) показана (упрощѐнная) диаграмма графа
( ; )
V

Gr
со словарѐм вершин
1 2
3 4
5 6
, , , , ,
V
v v v v v v

и матрицей смежности
6 6
0 1
1 0
0 0
0 0
0 1
0 0
0 1
0 0
1 0
(
)
0 0
1 1
1 0
0 0
0 0
0 0
0 0
0 0
0 0
Mtr
i
j
m










 











.►
Если в вершину
v V

орграфа
( ; )
V

Gr
входит ровно
k
дуг, то говорят, что еѐ
позитивная валентность
( )
val v
k


. Если из вершины
v V

орграфа
( ; )
V

Gr
исходит ровно m дуг, то говорят, что еѐ негативная валентность
( )
val v
m


. Число
( )
( )
( )
val v
val v
val v




называется валентностью вершины
v V

. Если
( )
0
val v


, то вершину
v V

называют источником, если
( )
0
val v


– стоком, если же
( )
( )
0
val v
val v




– глухим источником.

17
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Список
0 1
1 2
1
((
,
), ( ,
),..., (
,
))
k
k
u u
u u
u
u




из
k
последовательных дуг орграфа
( ; )
V

Gr
называется его путѐм с началом в вершине
0
u
V

и окончанием в вершине
k
u
V

. Этот же путь будет обозначаться и списком вершин
0 1
2 1
(
,
,
,...,
,
)
k
k
u u u
u
u




, в котором каждая непосредственно следующая вершина смежна с предыдущей. Число
|
| |
|
k






называется длиной этого пути. Если
0
k
u
u

, то этот такой путь называется
контуром или циклом, в котором любая вершина может считаться начальной или конечной. Если же в этом цикле все вершины
1 2
1
,
,...,
,
k
k
u u
u
u

попарно различны, то такой цикл называется простым. В частности, если
0
k

, то такой простой цикл называется петлѐй. Путь, не являющийся циклом, при проходе которого нет повторяющихся вершин, называется простым путѐм, в противном случае – составным
путѐм, в котором, в качестве его составляющей, обязательно содержится цикл.
Определение 3.1 (ациклического орграфа). Орграф, в котором нет циклов, называется ациклическим.►
Орграф, диаграмма которого показана на рис. 1 не является ациклическим, поскольку содержит петлю. Кроме того, на этой диаграмме путь
5 1
2 4
3 2
( ,
,
,
,
,
)
u u u u u u
является составным, т.к. содержит цикл
2 4
3 2
(
,
,
,
)
u u u u
Определение 3.2 (дерева). Конечный ациклический орграф с одним источником, в котором любая вершина, не являющаяся источником, имеет единичную позитивную валентность, называется деревом. Источник дерева называется его корнем, стоки –
листьями.►
Теорема 3.1. Если орграф является деревом, то для его двух различных вершин – либо нет соединяющего их пути, либо такой путь есть и он единственен.►
На рис. 3 показана упрощѐнная диаграмма орграфа-дерева.

18
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Рис.3
Рис.4
Определение 3.3 (логической сети). Пусть
( ; )
V

Gr
– такой конечный ациклический орграф с n не глухими источниками и одним стоком, в котором любые два пути соединяющиеся источники с его вершиной, не являющейся источником, имеют одинаковую длину. Тогда такой орграф называется логической сетью.►
На рис. 4 показана упрощѐнная диаграмма логической сети с тремя источниками, которые, как и сток, отмечены особыми (двойными) стрелками.
3.2. Неориентированные графы. Контактные сети
Пусть в конечном орграфе
( ; )
V

Gr
бинарное отношение

является антирефлексивным
(т.е.
( , )
v v


для любой вершины
v V

) и антисимметричным ( ( , )
v u


, если
( , )
u v


).
Следовательно, орграф
( ; )
V

Gr
не имеет петель и две его вершины не могут быть взаимно смежными. В этом случае орграф
( ; )
V

Gr
, определяет конечный неориентированный граф
( ; )
Gr V

, называемый, кроме того, разориентацией орграфа
( ; )
V

Gr
. Граф
( ; )
Gr V

имеет тот же словарь вершин и его неориентированные рѐбра собраны в совокупность
( , ) {{ , } { , }: ( , )
}
V
u v
v u
u v





R
. Следовательно, для неориентированного графа
( ; )
Gr V

бинарное отношение
V V

 
имеет вид
{( , )
: ( , )
( , )
}
u v
V V
u v
или v u




 


и симметричная матрица Mtr

с нулями на главной диагонали определяет неориентированное понятие смежности его вершин. По

19
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев аналогии с орграфом
( ; )
V

Gr
в графе
( ; )
Gr V

вводятся понятия путей и их длин, но понятие смежности вершин теряет ориентацию. Поэтому для вершин графа вводится только одно понятие (общей) валентности, но нельзя ввести позитивные и негативные валентности.
На рис. 5 показана упрощѐнная диаграмма орграфа, для которого на рис. 6 приведена упрощѐнная диаграмма его разориентации. На упрощѐнной диаграмме разориентации особыми стрелками указаны источник и сток исходного орграфа.
Рис.5
Рис.6
Определение 3.4 (контактной сети). Пусть граф
( ; )
V

Gr
является разориентацией конечного ациклического орграфа с одним не глухим источником q V

и одним стоком
e
V

. Тогда граф
( ; )
V

Gr
, в котором вершина q V

является входом и вершина
e
V

–
выходом, называется контактной сетью. Для обозначения этой сети используется выражение:
( ; | , )
V
q e

Gr
.►
На рис. 6 показана упрощѐнная диаграмма контактной сети, полученной разориентацией орграфа, упрощѐнная диаграмма которого приведена на рис. 5. На диаграмме контактной сети, показанной на рис. 6, вход и выход отмечены особыми
(двойными) стрелками.
3.3. Конечные мульти-орграфы. Язык конечного мульти-орграфа
Пусть задан алфавит
1
,...,
k
A
a
a

с совокупностью
A его букв и словарь V конечного формального языка V , на котором определѐн список бинарных отношений
1
ˆ
ˆ
ˆ
( ,...,
)
k
A
a
a

, индуцируемых их матрицами.
Тогда определѐн набор из
k
орграфов

20
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
1
ˆ
ˆ
ˆ
( ; )
(
( ;
),...,
( ;
))
Gr
Gr
Gr
k
V A
V a
V a

, называемый конечным мульти-орграфом. В этом мульти-орграфе
V
– словарь его вершин и
ˆ
ˆ
( , ) {
: (
1, | ( , )
}
R
j
j
a
V A
u
v
j
k u v
a
 
 

– совокупность его ориентированных рѐбер-дуг. Если
ˆ
ˆ
j
a
A

и
ˆ
( , )
R
j
a
u
v
V A
 
, то
u
V

– начало и
v V

конец этого ребра и, кроме того, вершина
v V

является
ˆ
j
a
- смежной с вершиной
u
V

. Следовательно, в отличие от обычного орграфа, вершина мульти-орграфа может иметь несколько типов смежности с другой вершиной или сама с собой. Для наглядного представления мульти-орграфа, как и для обычного орграфа, используется его диаграмма. Для иллюстрации, на рис.7 показан пример диаграммы конечного мульти-орграфа. Как и для обычного орграфа, в мульти-орграфе
ˆ
( ; )
Gr V A определяется путь с началом в вершине
0
u
V

и концом в вершине
m
u
V

в виде набора его дуг
1 2
0 1
1 2
1
(
,
,...,
)
m
m
m
b
b
b
u
u u
u
u
u







, где
1
,...,
m
b
b
A

. Этот путь длиной |
| m



связывает вершину
0
u
V

с вершиной
m
u
V

В мульти-орграфе
ˆ
( ; )
Gr V A могут выделяться непустые совокупности
0
V
V

и
1
V
V

начальных и заключительных его вершин, соответственно. В этом случае для такого мульти-орграфа используется обозначение
0 1
ˆ
( ; |
,
)
Gr V A V V
, вершины
0 0
v
V

и
1 1
v
V

называются начальной и заключительной, соответственно. Кроме того, для обозначения совокупности путей, связывающих его начальные и заключительные вершины, используется выражение
0 1
(
,
)
V V

Определение 3.5 (языка мульти-орграфа). Для совокупности путей
0 1
(
,
)
V V

мульти- орграфа
0 1
ˆ
( ; |
,
)
Gr V A V V определено отображение
*
0 1
:
(
,
)
V V
A



в универсальный
A - язык
*
A следующим образом.
Если
0 0
u
V

,
1
m
u
V

и
1 2
0 1
1 2
1 0
1
(
,
,...,
)
(
,
)
m
m
m
b
b
b
u
u u
u
u
u
V V








, то
*
1
(
)
m
b
b
A





Формальный A -язык
*
0 1
{ (
) :
(
,
)}
V V
A







, дополненный пустым словом, если
0 1
V
V

 
, называется языком мульти-орграфа
ˆ
( ; )
Gr
Gr V A

и для него используется обозначение
(
)
Gr
Lng
.►

21
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Рис.7
Рис.8
Пример 3.2 (мульти-орграфа и его языка). На рис. 7 и рис. 8 показаны диаграммы орграфов
ˆ
( ; )
Gr V a и
ˆ
( ; )
Gr V b
, соответственно. Из этих орграфов образован мульти-орграф
ˆ
ˆ
( ; , | 1 , 3, 4 )
Gr
Gr V a b

, диаграмма которого приведена на рис. 9. Входные и заключительные вершины этого мульти-орграфа отмечены на диаграмме особыми
(двойными) стрелками.
Из анализа диаграммы мульти-орграфа
Gr
следует, что его язык
(
)
Gr
Lng
имеет вид:
(
)
{
:
} {
:
} { } { }
,
Gr
m
m
Lng
ab a m
ab ab m
bb
b
a b










, где
{
:
0}
j
j




,
m
m раз
b
b b


для
m


и
0
b


– пустое слово.►
Рис.9
Замечание 3.1 (об искусственных языках). Формальные языки, порождѐнные конечными мульти-орграфами, относятся к типу искусственных языков, используемых в языках

22
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев программирования. Среди формальных языков искусственные языки образуют более узкий класс. Основное требование к языкам этого узкого класса состоит в том, чтобы они были разрешимы, т.е. распознаваемы с помощью соответствующих алгоритмов. Такое требование обусловлено тем, что тексты практических программ достаточно велики и, фактически, недоступны для проверки на корректность (синтаксическую правильность) человеком. Следовательно, анализ корректности текстов таких программ должен осуществляться автоматически с помощью тех или иных алгоритмов, реализуемых на современных компьютерах.
Следует отметить, что среди искусственных языков языки, порождѐнные мульти- орграфами и названные регулярными, являются самыми простыми и используются для создания простейших конструкций языков программирования. Распознавания таких языков происходит с помощью соответствующих автоматов, о которых будет рассказано в последующих разделах.►
4. Детерминированные и недетерминированные автоматы
Пусть A и B – два квази-алфавита, т.е. два неупорядоченных «алфавита», и V – словарь
(конечного) формального языка V . Кроме того, заданы отображения
: A V
V

 
и
: A V
B

 
. Тогда пятерка
( , , , , )
A B V
 
 
определяет (конечный) автомат Мили, в котором квази-алфавиты A и B называются его алфавитами входа и выхода, соответственно, язык V – совокупностью его состояний, отображения
: A V
V

 
и
: A V
B

 
– его функциями перехода по состояниям и выхода, соответственно. В этом случае автомат Мили называют (конечным) детерминированным автоматом. Если же функция

не определена для некоторых пар из совокупности
A V

или на некоторых парах этой совокупности – многозначна, то такой автомат

называется (конечным) недетерминированным автоматом.
Автомат Мили

называется автоматом Мура, если есть такое отображение
:V
B


, что ( , )
( ( , ))
a v
a v

 

для любых
a
A

и
v V

Если в автомате Мили

всего одно состояние, т.е. |
| 1
V

, то автомат

называется
дискретным преобразователем.
Автомат Мили

, в котором алфавит входа состоит из единственной буквы, называется автономным автоматом Мили.