Классификация состояний и подавтоматов

Дуга относительно данного состояния, например, σ _i, может быть заходящей в σ _i, если она направлена к σ _i из другого состояния, или исходящей из σ _i, если она направлена от σ _i к другому состоянию, или петлей, если она выходит из σ _i и входит в σ _i. На рис. 2.3 показаны эти три типа дуг.

Состояние, в котором отсутствуют заходящие и (или) исходящие дуги, может быть одним из следующих типов:

(1) преходящее состояние — состояние, которое не имеет заходящих дуг, но имеет, по крайней мере, одну исходящую дугу; из этого состояния может быть осуществлен переход, по крайней мере, в одно другое состояние, но после выхода из этого состояния, в него нельзя попасть ни из какого другого; (2) тупиковое состояние — состояние, которое не содержит исходящих дуг, но содержит, по крайней мере, одну заходящую дугу; в такое состояние может быть осуществлен переход, по крайней мере, из одного другого состояния, но после перехода в это состояние из него нельзя осуществить переход ни в одно другое состояние; (3) изолированное состояние — состояние, которое не содержит ни заходящих, ни исходящих дуг; из такого состояния нельзя перейти ни в какое другое и в него нельзя попасть ни из какого другого состояния. На рис. 2.4 приведен автомат А2, в котором состояния 1 и 5 являются преходящими, состояния 2 и 4—тупиковыми, а состояние 6 — изолированным.

Любое разбиение множества состояний автомата на два или большее число подмножеств может быть, очевидно, выполнено путем заключения представленных графом переходов

состояний каждого подмножества в отдельный «прямоугольник», рассматриваемый как подавтомат. На рис. 2.5 и

в таблице 2.4 представлен автомат ЛЗ, множество состояний которого S= {1, 2, 3, 4, 5, 6, 7, 8, 9} разделено на подмножества S₁={1,4, 7}, S₂={2, 5, 8} и S₃={3, 6, 9}; три подавтомата, изображенные в виде прямоугольников, обозначены на рисунке символами S₁, S₂ и S₃.

Рассматривая каждый подавтомат как одно «сверхсостояние», преходящий, тупиковый или изолированный подавто

маты могут быть определены точно так же, как преходящее, тупиковое и изолированное состояние с заменой слова «состояние» на слово «подавтомат», именно: (1) преходящий подавтомат можно перевести, по крайней мере, в один другой подавтомат, но он не может быть достигнут после того, как оставлен; (2) тупиковый подавтомат может быть достигнут, по крайней мере, из одного другого подавтомата, но не может быть покинут после того, как он достигнут; (3) изолированный подавтомат не может быть достигнут ни из одного другого подавтомата и не может привести ни в какой другой подавтомат. Граф переходов часто позволяет визуально определить, составляет ли определенное подмножество множества состояний преходящий, тупиковый или изолированный подавтомат, и, следовательно, сделать заключение об относительной доступности этого подмножества. Например, из рис. 2.5 можно легко заключить, что S₁ — тупиковый подавтомат, S₂ — преходящий подавтомат, a S₃ — изолированный подавтомат.

Пусть G _k (S _i) обозначает множество всех состояний автомата М, в которые можно попасть из любых состояний множества S _i = {σi₁, σi₂,..., σi_r} при подаче на вход последовательности длины k или меньше. В частности, G₀(S _i) = S _i. Множество G_i(S _i) есть объединение S _i и всех состояний, указанных в строках σi ₁, σi ₂,..., σi _r, подтаблицы s _v+1 таблицы переходов М. С другой стороны, G₁(S _i) может быть определено путем просмотра графа переходов автомата М. Если задано G _k-l (S _i), k ≥1, то G _k (S _i) может быть определено из соотношения

Если G _k (S _i) = G _k-1 (S _i), то G _k+u (S _i) = G _k-l (S _i) для всех неотрицательных целых и; следовательно, G _k (S _i) составляет множество всех состояний, в которые можно попасть из S _i если на вход подавать последовательности любой длины. Определение этого множества, обозначаемого просто G(S _i), может быть теперь описано при помощи следующего алгоритма.

Алгоритм 2.1. Дано S _i, найти G(S _i). (1) Пусть G ₀ (S _i) = S i. Полагаем k =l. (2) Определяем G _k (S _i) = G₁(G _k-1 (S _i)). (3) (а) Если G _k (S _i) ≠ G _k-1 (S _i), увеличиваем k на 1 и возвращаемся к (2). (б) Если G _k (S _i) = G _k-1 (S _i), то G _k (S_i) = G(S_i).

Если G _k (S_i) ≠ G_k-l(S_i), то G_k(S_i) должно содержать, по крайней мере, на один элемент больше, чем G_k-l(S_i). Так как мощность G_k(S_i) не может превышать общее число n состояний автомата М, то G _k (S _i) должно равняться G _k-l (S _i) для k ≤ n – r + 1, где r — мощность для автомата A3 множества S i. Следовательно,

G(S _i)=G _n-r (S _i). (2.8)

Это значит, что алгоритм 2.1 требует не более чем n - r итераций пункта 2. Таблица 2.5

иллюстрирует применение алгоритма к автомату AЗ, изображенному на рис. 2.5, для S _i = {5, 6}, который дает G(5, 6)={1, 3, 4, 5, 6, 7, 9}.

Если S_i состоит из одного состояния σ _i, то G (σ _i) называется σ _i -достижимым множеством и представляет собой множество всех состояний, в которые можно попасть из состояния σ _i.

Теорема 2.2. Пусть σ _i и σ _j — два состояния в автомате с n состояниями. Если σ _j вообще достижимо из σ _i, то оно достижимо при подаче входной последовательности длиной не более n - 1.

Доказательство. При Si = { σ _i } мощность r -множества S _i равна единице и выражение (2.8) принимает вид

G(σ _i) = G _n-l (σ _i). (2.9)

Это означает, что σ _i - достижимое множество является множеством всех состояний автомата М, достижимых из σ _i при подаче входной последовательности длины n - 1 или меньше. Если известно, что начальное состояние автомата М принадлежит непустому множеству S _i, которое составляет тупиковый или изолированный подавтомат, то М можно упростить путем исключения всех состояний, которые не принадлежат множеству S _i, и всех дуг, начинающихся в этих состояниях. Полученный автомат хотя и необязательно является адекватным представлением исходной системы во все моменты времени, но адекватен ей в смысле поведения в будущем. Это вытекает из того, что исключенные состояния никогда не могут быть достигнуты из начального состояния, и, следовательно, они в данном случае излишни. Например, если известно, что начальным состоянием автомата ЛЗ, изображенного на рис. 2.5, является состояние 1, то точный анализ поведения автомата ЛЗ в будущем может быть проведен, несмотря на- то, что состояния 2, 3, 5, 6, 8, 9 и начинающиеся в них дуги будут исключены из графа переходов.