Читать «Математический аппарат инженера» онлайн - страница 65

С помощью графа автомата легко выделить следующие характерные типы его состояний:

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

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

3) изолированное состояние, из которого нельзя перейти ни в какое другое состояние и в него нельзя попасть ни из какого другого состояния (соответствующая вершина содержит только петлю).

Аналогичные определения можно дать для некоторых совокупностей состояний, рассматриваемых как подавтоматы. Если начальное состояние автомата М принадлежит непустому множеству S_i состояний, которое составляет тупиковый или изолированный подавтомат, то M можно упростить исключением всех состояний, которые не принадлежат множеству S_i, и всех дуг, начинающихся в этих состояниях.

Пусть М₁, М₂ и M₃ - соответственно преходящий, тупиковый и изолированные подавтоматы автомата М, которые характеризуются множествами состояний S₁, S₂ и S₃. Очевидно, выделение таких подавтоматов соответствует разбиению множества S состояний автомата М на непересекающиеся подмножества S₁, S₂ и S₃, представляющие собой классы эквивалентности ( S₁ ∪ S₂ ∪ S₃ = S и S₁ ∩ S₂ ∩ S₃ = ∅ ). Как следует из обобщенного графа (рис. 237), матрица соединения автомата может быть представлена в виде:

,

- 570 -

где μ₁₁, μ₂₂, μ₃₃ - матрицы подавтоматов М₁, М₂ и М₃; μ₁₂ - матрица, характеризующая переходы от состояний преходящего автомата М₁ к состояниям тупикового автомата М₂. Отсюда следует, что разбиение автомата М на подавтоматы М₁, М₂ и М₃ можно осуществить преобразованием его матрицы соединений к стандартному виду путем перестановки соответствующих строк и столбцов. Например, для автомата, граф которого изображен на рис. 238, имеем:

Рис. 237. Обобщенный граф конечного автомата.

Рис. 238. Граф конечного автомата к примеру разбиения на подавтоматы.

Отсюда следует, что S₁ = {3, 6} составляет преходящий подавтомат, S₂ = {2, 4, 7} - тупиковый подавтомат и S₃ = {1, 5} - изолированный подавтомат. Если начальное состояние принадлежит множеству S₂, то можно упростить автомат, исключив состояния S₁ ∪ S₃ = {3, 6, 1, 5}, а в случае принадлежности начального состояния множеству S₃ автомат упрощается исключением состояний S₁ ∪ S₂ = {3, 6, 2, 4, 7}.

6. Синтез конечных автоматов. Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x(ν) и s(ν) в выходные переменные y(ν) и s(ν + 1) в соответствии с заданными характеристическими функциями s(ν + 1) = δ (x(ν), s(ν)) и y(ν)= λ (x(ν), s(ν)). Для сохранения состояний s(ν + 1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.