ВУЗ:
Составители:
Рубрика:
100
Заметим, что дуги, выходящие из любой вершины графа переходов,
содержат полное число p пар вход-выход, равное мощности входного ал-
фавита. Так, каждая вершина графа переходов автомата А1 содержит на
выходящих из неё дугах по пять таких пар, поскольку мощность входно-
го алфавита этого автомата равна пяти.
Непосредственное преимущество графа переходов состоит в том, что
он облегчает определение реакции автомата на входную последователь-
ность. Например, реакцией автомата А1 на входную последовательность π,
u, n, λ, λ, d, π при начальном состоянии 3 будет выходная последователь-
ность 0, 0, 0, 0, 0, 0, 1, которая легко определяется по рис. 53. При этом ав-
томат последовательно побывает в состояниях 1, 3, 4, 4, 4, 5 и 1.
В терминах графов переходов легко ввести классификацию состоя-
ний и подавтоматов, разделив все дуги на входящие, выходящие и петли.
Преходящим состоянием называется состояние, соответствующее
вершине графа переходов, которая не имеет входящих дуг, но имеет по
крайней мере одну выходящую дугу. Тупиковое состояние соответствует
вершине графа, которая не имеет выходящих дуг, но имеет по крайней
мере одну входящую дугу. Изолированное состояние определяет верши-
на без входящих и без выходящих дуг. Автомат А2, граф переходов кото-
рого приведён на рис. 54, имеет преходящие состояния 1 и 5, тупиковые
состояния 2 и 4, изолированное состояние 6.
Любое разбиение множества S состояний автомата на подмножества
определяет подавтоматы этого автомата.
2
1
5
4
3
)0/()0/()0/()0/( λ∨∨∨ und
)0/(π
)0/()0/()0/(
λ
∨
∨
nd
)0/(
π
)0/(u
)0/(
π
)0/(
π
)1/(π
)0/()0/()0/( λ∨∨ ud
)0/(n
)0/()0/()0/( λ∨∨ un
)0/()0/()0/( λ∨∨ un
)0/(d
)0/(d
Рис. 53
Страницы
- « первая
- ‹ предыдущая
- …
- 98
- 99
- 100
- 101
- 102
- …
- следующая ›
- последняя »
