Дискретная математика. Громов Ю.Ю - 110 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

110
1 2 3
4
A
)2(
4
′
A
=
π
12
π
23
π
31
π
13
π
31
π
12
0
1
0 π
23
π
31
π
12
0
2
0 0 π
31
π
12
π
23
3
имеет полные контуры π
12
π
23
π
31
, π
23
π
31
π
12
и π
31
π
12
π
23
.
Задачи и упражнения
1. Постройте матрицу переходов для каждого конечного автомата
из упр. 1, а – в параграфа 18.
2. В автомате А, заданном приведённой ниже матрицей переходов:
а) определите преходящие, тупиковые и изолированные состояния;
б) определите G
1
(5, 7) и H
1
(2, 3); в) путём изменения порядка строк и
столбцов матрицы переходов определите, составляют ли множества со-
стояний {1, 2, 4, 7} и {3, 5, 6, 8} пару из преходящего и тупикового по-
давтоматов, пару изолированных подавтоматов или пару подавтоматов,
не принадлежащих ни к одному из указанных типов.
1 2 3 4 5 6 7 8
)0/()1/( β∨α
0 0 0 0 0 0 0 1
0
)0/(α
0
)1/(β
0 0 0 0 2
0 0
)1/()1/( β∨α
0 0 0 0 0 3
A =
0 0
)1/(α
0
)0/(β
0 0 0 4
0 0
)0/(α
0 0 0 0
)1/(β
5
0 0 0 0 0
)0/()1/( β∨α
0 0 6
0 0 0 0
)0/(β
0 0
)1/(α
7
0 0 0 0 0
)1/()0/( β∨α
0 0 8
3. Для автомата А из предыдущей задачи: а) постройте
A
,
2
A
,
3
A
;
б) постройте
)1(
′
A
,
)2(
′
A
, ...,
)7(
′
A
; в) установите, что этот автомат не
имеет полных контуров.

Страницы