ВУЗ:
Составители:
174
Отсюда мощность класса явно минимальных автоматов, не со-
держащего изоморфных автоматов, определяется формулой
∏
−
=
−=
1
0
),,(
)(
!
q
k
n
nq
M
qmn
km
q
q
N .
Проще всего автомат изоморфный данному получить, если на
графе автомата по-новому переобозначить вершины (рис. 5.13).
Граф автомата
удобно использовать и
при классификации со-
стояний подавтоматов.
Роль графа автомата в
теории автоматов по-
добна роли, которую играет изображение схемы в теории электриче-
ских цепей. Граф преобразует абстрактную модель
в графическое
изображение, а это усиливает интуицию исследователя.
Приведем возможную классификацию внутрен-
них состояний автоматов и подавтоматов данного ав-
томата. Для любого состояния s
i
возможны следую-
щие отношения с дугами графа автомата: дуга вхо-
дит, исходит или является петлёй (рис. 5.14).
Состояние, которое не имеет входящих дуг, но имеет хотя бы
одну исходящую, называют преходящим. Из этого состояния можно
выйти, но нельзя вернуться.
Состояние, которое не содержит исходящих дуг, но имеет хотя
бы одну
входящую дугу, называют тупиковым. В это состояние
можно попасть, но уже нельзя выйти.
Состояние, которое не имеет ни входящих, ни исходящих дуг,
называют изолированным.
S
2
S
1
S
3
S
2
S
3
S
1
Рис. 5.13
S
i
Рис. 5.14
Страницы
- « первая
- ‹ предыдущая
- …
- 176
- 177
- 178
- 179
- 180
- …
- следующая ›
- последняя »
