Математические основы теории систем

Если идет речь о системе управления, то энергетические затраты на выработку управления, как правило, малы по сравнению с энергопотреблением объекта управления, и в этом случае их просто не принимают во внимание в классе обычных систем. Но в некоторых случаях управляемая и управляющая части могут потреблять соизмеримое количество энергии и питаться от одного источника. При этом возникает нетривиальная задача перераспределения огра-

33

·····························································

Контрольные вопросы по главе 1

·····························································

1.Перечислите основные свойства систем.

2.Приведите классификацию абстрактных моделей.

3.Приведите классификацию материальных моделей.

4.Назовите различия между моделью и оригиналом.

5.В чем сходство между моделью и оригиналом?

6.Что такое модель «черного ящика»? Приведите пример, когда эта модель единственно возможна.

7.Что такое модель состава системы? Приведите пример:

а) моделей, имеющих одинаковый элементный состав, но различающихся делением на подсистемы;

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

8.Дайте второе определение системы.

9.Что такое динамическая модель «черного ящика»? Приведите пример.

10.Что такое динамический вариант модели состава? Приведите пример.

11.Что такое динамический вариант структурной схемы?

12.Дайте понятия состояния системы и переменных состояния системы.

13.Приведите классификацию математических моделей систем.

14.Каковы основаные классификации систем?

15.Приведите классификацию систем по типам переменных (входных, выходных и состояния).

16.Назовите виды систем в соответствии с ресурсным обеспечением. Приведите пример системы: а) малой и сложной; б) большой и простой; в) большой и сложной.

34

2 Автоматное описание систем. Теория конечных автоматов

В том случае, если множества входных X, выходных Y и внутренних переменных Q являются конечными, мы приходим к так называемому автоматному описанию системы. Для этого случая разработана достаточно разветвленная, хорошо формализованная теория конечных автоматов. Конечными автоматами можно описывать любые цифровые устройства и элементы. Анализ и синтез цифровых устройств также успешно может быть осуществлен с применением теории конечных автоматов. Для изучения этого раздела достаточно знать методы формальной логики, теорию множеств, теорию графов и основы абстрактной алгебры.

Естественно, что и пользоваться при этом мы будем понятиями, определениями и терминологией (то есть профессиональным языком), принятыми в соответствующих разделах дискретной математики [7].

2.1 Основные понятия. Способы задания автоматов

2.1.1 Определение абстрактного автомата

Пусть X ={x1, x2,... xm} и Y ={y1, y2,... yk } – два произвольных множества

элементов, которые будем называть алфавитами, а их элементы – буквами алфавита. Конечную упорядоченную последовательность букв назовем словом в данном алфавите. Обозначим X* и Y – множества всех слов в алфавитах X и Y соответственно. Тогда произвольное преобразование дискретной информации можно задать как однозначное отображение S множества слов X* во множество слов Y* . Отображение S называется алфавитным отображением или алфавитным оператором, а алфавиты X и Y – входным и выходным алфавитами

y Y* , такое, что y = S (x) . То есть S есть функция, область определения кото-

рой X*, а область значений – Y* .

В общем случае отображение S может быть частичным, т. е. не всюду определенным. Это позволяет рассматривать отображение S как оператор в од-

35

ном и том же расширенном алфавите Z = X Y . Частичное отображение S множества Z* в себя, определенное на словах, состоящих только из {x1…xm}, можно выбрать таким образом, что оно будет совпадать с отображением S множества X* в Y * . Любой абстрактный автомат реализует некоторый оператор S или индуцирует некоторое отображение S.

Условия, накладываемые на автоматные отображения, рассмотрим несколько позже, а сейчас отметим ряд допущений, связанных с понятием абстрактного автомата:

а) наличие произвольного числа отличных друг от друга состояний автомата и свойство мгновенного перехода из одного состояния в другое;

б) переход из одного состояния в другое оказывается возможным не ранее, чем через некоторый промежуток времени ∆ (∆ > 0 – интервал дискретности) после предыдущего перехода;

в) число различных входных и выходных сигналов конечно; г) входные сигналы − причина перехода автомата из одного состояния

в другое, а выходные сигналы – реакция автомата на входные сигналы и относятся они к моментам времени, определенным соответствующим переходом автомата из состояния в состояние.

Учитывая это, можно интерпретировать автомат как устройство, работающее в дискретном времени t' = n×∆ (n N0 ) . На каждый входной сигнал x(t)

автомат реагирует выходным сигналом y(t), где t = ∆t′ – нормированное время.

Связь между входом и выходом определяется текущим состоянием автомата q и задается функцией выхода y = λ(q,x), а переход автомата из одного состояния

в другое – функцией переходов q = δ(q, x).

·····························································

Определим абстрактный автомат как пятерку объектов: A = (X ,Y,Q,λ,δ),

где X ={x1, x2,... xm} − входной алфавит или множество входных состояний; Y ={y1, y2,... yk } − выходной алфавит или множество

выходных состояний; Y ={y1, y2,... yk }− множество внутренних со-

36

стояний; δ:Q× X →Q – функция перехода; λ:Q× X →Y – функ-

ция выхода.

·····························································

Если Q < ∞ , то мы имеем дело с конечным автоматом, если Q – множество счетное – то с бесконечным. Если начальное состояние зафиксировано (например, q1), то автомат называется инициальным. Таким образом, по неинициальному автомату можно n способами задать инициальный автомат.

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

Сдругой стороны, описание реального устройства, функционирующего

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

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

ни, отличный от нулевого, на вход автомата поступает входной сигнал x(t) –

произвольная буква входного алфавита x(t) X , а на выходе возникает некоторый выходной сигнал y(t) – буква выходного алфавита y(t) Y . Для данного автомата его функции δ и λ могут быть определены не только на множестве Х всех входных букв, но и на множестве X* всех входных слов. Действительно, для любого входного слова x = xi1 xi2 ...xik справедливо соотношение:

или, используя индуктивное определение:

37

..., x(l) = xik , то есть входного слова x = xi1 xi2 ...xik на основании известных функ-

y = yj1 yj2 ...yjk = λ(q1,xi1 )λ(q1,xi1xi2 )...λ(q1,xi1...xik ).

Соотнося с каждым входным словом соответствующее ему выходное, получим искомое отображение, которое и является автоматным отображением, или автоматным оператором. Если результатом применения оператора к слову x будет выходное слово y, то это обозначается так: S (q1,x) = y или S (x) = y .

Автоматное отображение можно определить и индуктивно:

·····························································

Автоматное отображение обладает двумя свойствами, непосредственно следующими из определения:

1)слова x и y = S (x) имеют одинаковую длину;

2)если x = x1x2 и S (x1x2 ) = y1y2 , где x1 = y1 = i , то S (x1)= y1 . Иначе говоря, образ отрезка длины i равен отрезку образа той же длины.

Свойство второе означает, что автоматные операторы – операторы без предвосхищения, то есть операторы, которые перерабатывают слово слева направо, не «заглядывая» вперед.

·····························································

38

Таким образом, одна из интерпретаций абстрактного автомата – это некоторое цифровое вычислительное, управляющее или преобразовательное устройство. Входная буква – это входной сигнал (комбинация сигналов на всех входах устройства), входное слово – последовательность входных сигналов, поступающих в дискретные моменты времени t =1,2,3,… Выходное слово – последовательность выходных сигналов, выдаваемых автоматом, внутреннее состояние автомата – комбинация состояний запоминающих элементов устройства.

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

2.1.2 Задание автоматов

Поскольку функции δ и λ определены на конечных множествах, то их можно задать таблицами. Обычно две таблицы (для функции δ и для функции λ) сводят в одну таблицу δ×λ:Q× X →Q×Y и называют такую таблицу автоматной таблицей, или таблицей переходов автомата. В этой таблице на пересечении столбца с входной буквой xi и строки с состоянием qj стоит пара − состояние ql, в которое переходит автомат из состояния qj по входной букве xi, и выходная буква yk, которая при этом выдается автоматом.

Часто вместо автоматной таблицы для задания автомата используют так называемую матрицу соединений автомата. Это матрица n×n, строки

истолбцы которой соответствуют различным состояниям автомата. На пересечении qi-й строки и qj-го столбца стоит буква (или дизъюнкция букв) входного алфавита xl X , вызывающая переход автомата из состояния qi в состояние qj,

ив скобках (можно через запятую, тире или слеш) – буква (или дизъюнкция букв) выходного алфавита yk Y , которая появляется при этом на выходе ав-

томата. Если ни одна из букв входного алфавита не переводит состояние qi в qj, то ставится прочерк или ноль. В любой строке каждая буква входного алфавита встречается не более одного раза (условие однозначности переходов).

Еще один способ задания автоматов – ориентированный мультиграф, называемый графом переходов, или диаграммой переходов. Вершины графа переходов соответствуют состояниям автомата. Если δ(qi,xj )= qk и λ(qi,xj )= yl ,

39

то из вершины qi в вершину qj ведет ребро, на котором написаны пара xj, yl. Для любого графа переходов выполняются следующие условия корректности:

На графе переходов наглядно представимы все функции, определяемые формулами (2.1)−(2.5). Если зафиксирована вершина qi, то всякое слово x = xi1 xi2 ...xik однозначно определяет путь длины k из этой вершины (обозначим

его qi,x), на k ребрах которого написаны xi1 xi2 ...xik . Поэтому δ(qi,x) − это последняя вершина пути qi ,x; λ (qi ,x) − выходная буква, написанная на последнем ребре пути qi,x, а отображение S (qi ,x) − слово, образованное выходными буквами на k ребрах пути qi,x.

······················· Пример 2.1························

Пусть автомат задан своей автоматной таблицей (табл. 2.1):

Таблица 2.1 – Автоматная таблица к примеру 2.1

Здесь и в дальнейшем, если это не вызовет разночтений, внутренние со-

Y = {y1, y2 , y3}.

Матрица соединений данного автомата приведена ниже (табл. 2.2).