Какие состояния автомата называются недостижимыми?

Пусть в некоторое состояние автомата не существует пути из начального состоя­ния. Иными словами, в эти состояния автомат не может попасть. Такие состояния автомата называются недостижимыми, остальные — достижимыми. Очевидно, что недостижимые состояния и переходы из них можно отбросить: они не влияют на поведение конечного автомата. Дадим формальное определение.

Определение. Пусть А ^в <S, X, Y, s₀, 8, К> — конечный автомат. Состояние se S называется достижимым тогда и только тогда, когда (3ae X *)8*(s₀, a) = s (то есть под воздействием какой-либо цепочки входных сигналов автомат попада­ет в это состояние). Состояние конечного автомата является недостижимым тогда и только тогда, когда под воздействием любой входной цепочки автомат не переходит в это состояние: Недостижимо (s) <=> (VaE X*)8*(s₀, а) Ф s.

Рисунок 4.5 Два конечных автомата

Достижимое множество состояний конечного автомата A ^e <S, X, Y, s₀,8, Х> стро­ится с помощью алгоритма, основанного на индукции. Алгоритм разобьем на по­следовательные шаги. На i-м шаге будем строить множество Qi состояний, достижимых из начального состояния автомата некоторой входной цепочкой длины не более чем i. Очевидно, что Qo^e {s₀}. Для любого i очевидно определение qi+i ⁼Qi ^u(^us6Qi ^uxcx S(^s»^x))- Очевидно также, что не более чем за [S | шагов qu+i ⁼ Qk- Это множество состояний Qk будет включать в себя все достижимые состояния автомата A ^e <S, X, Y, s₀, 5, А>.

Дата добавления: 2015-07-26; просмотров: 295; Нарушение авторских прав

Мы поможем в написании ваших работ!