ВУЗ:
Составители:
Рубрика:
81
- изолированное состояние, из которого нельзя перейти ни в какое
другое состояние и в него нельзя попасть ни из какого другого состояния ,т.е.
соответствующая вершина содержит только петлю.
Аналогичные определения можно дать и для некоторых совокупностей
состояний, рассматриваемых как подавтоматы. Если начальное состояние
автомата М принадлежит непустому множеству S состояний, которое
составляет тупиковый или изолированный подавтомат, то М можно
упростить, исключив все состояния, которые не принадлежат множеству S и
всех дуг, начинающихся в этих состояниях.
Пусть М
1
, М
2
, М
3
- соответственно преходящий , тупиковый и изо-
лированный подавтоматы, составляющие автомат М, обобщенный граф
которого показан на рис.3.7.
Подавтоматы М
1
, М
2
, М
3
характеризуются множествами состояний
µ
12
- матрица, характеризующая переход от состояний преходящего
автомата М
1
к состояниям тупикового автомата М
2
,
µ
22
- матрица подавтомата М
2
'
µ
33
- матрица подавтомата М
3
.
Отсюда следует, что разделение автомата М на подавтоматы М
1
, М
2
, М
3
можно осуществить преобразованием его матрицы соединений к
стандартному виду путем перестановки соответствующих строк и столбцов.
Эта операция достаточно легко формализуется и может быть выполнена с
помощью ЭВМ.
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
