Главная > Методы обработки данных > Введение в теорию конечных автоматов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.8. Определение множества состояний по внутренней структуре

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

значение любой зависимой переменной в любой тактовый момент, если известны значения входных переменных в этот момент и значения зависимых переменных в предыдущий тактовый момент. В таких случаях, как будет показано ниже, существует методика определения множества состояний системы.

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

На основании § 1.4 входные переменные можно представить одной переменной с алфавитом

где является алфавитом выходные переменные можно представить одной переменной z с алфавитом

где является алфавитом Аналогично зависимые переменные можно представить одной переменной у с алфавитом

где является алфавитом Тогда выражение (1.9) можно записать так:

Так как каждая выходная переменная является зависимой переменной, мы также имеем:

Для перехода от приведенных выше формул к стандартным характеристическим функциям конечного автомата определим переменную s следующим образом:

Тогда алфавит s, обозначаемый через 5, определяется формулой

Выражения (1.13) и (1.14) можно теперь записать так:

Из (1.15) и (1.17) получаем:

Как теперь видно, уравнения (1.18) и (1.19) выражают искомые характеристические функции. Следовательно, 5 составляет требуемое для описания заданной системы множество состояний.

Для примера рассмотрим схему, показанную на рис. 1.4. На вход от источника поступают импульсы со значением 0 и 1 со скоростью один импульс в каждые Т секунд.

Рис. 1.4. Схема с мажоритарным элементом.

Тактовые моменты выбраны совпадающими с моментами появления импульсов. Элементы — задержки, которые запоминают поступающие на них импульсы на Т секунд и затем передают их на следующий за ними элемент. Элемент представляет собой «мажоритарный орган», который выдает импульс 0 или 1 в зависимости от значения (0 или 1 соответственно) большинства поступающих на его входы импульсов. Нас интересует значение импульса на выходе Увы. Значение импульса на входе схемы в момент можно

принять в качестве входной переменной а значение импульса на выходе в момент в качестве выходной переменной . Значения импульсов, запомненные элементами в момент можно принять в качестве зависимых переменных и соответственно. Тогда имеем:

Из схемы видно, что значение z равно значению большинства переменных

Используя эти соотношения, можно определить значения функций:

Результаты вычислений представлены в таблице 1.1. Из определения s следует, что каждая строка части таблицы, состоящей из столбцов представляет собой состояние , а каждая строка части таблицы, состоящей из столбцов - состояние . Учитывая, что можно сделать вывод, что таблица 1.1 полностью описывает характеристические функции рассматриваемой схемы. Например, из таблицы легко определить (см. четвертую строку), что при состоянии в настоящий момент (001) и входном символе в этот же момент 1 выход в настоящий момент будет 1, а следующее состояние (110).

<< Предыдущий параграф Следующий параграф >>
Оглавление