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

• Название: Математические основы теории систем
• Дата: 20.01.2023
• Размер: 2.07 Mb.
• Имя файла: Математическая теория систем.pdf
• Тип: Учебное пособие; #895603
• страница: 5 из 35

x
справедливо соотношение
( )
(
)
(
)
1,
1 1,
1 2
1 2
(
)
( ,
)
,
,
,
i
i
i
i
i
i
k
k
q
q x x
x
q x
x
x
δ
= δ
= δ δ δ
x
(2.1.1) или, используя индуктивное определение:
− для каждой входной буквы
j
x функция ( , )
i
j
q x
δ
первоначально за- дана,
− для любого слова x∈X
*
и любой буквы
x
j
∈X
( ,
)
( ( , ), ).
i
j
i
j
q x
q
x
δ
= δ δ
x
x
(2.1.2)
C помощью такой расширенной функции δ можно также индуктивно определить и λ:
( ,
)
( ( , ), ).
i
j
i
j
q x
q
x
λ
= λ δ
x
x
(2.1.3)

40
Появление на входе конечной последовательности
1
(1)
i
x
x
=
,
2
(2)
,..., ( )
i
ik
x
x
x l
x
=
=
, то есть входного слова
1 2
i
i
ik
x x
x
=
x
на основании известных функций λ и δ, вызовет появление на выходе однозначной по- следовательности
1 2
(1)
, (2)
,..., ( )
j
j
jk
y
y y
y
y l
y
=
=
=
, которая соответству- ет выходному слову
2 1
1 1
1 1
1 2 1
( , ) ( ,
)... ( , ... )
k
k
j
j
j
i
i i
i
i
y y
y
q x
q x x
q x x
=
= λ
λ
λ
y
Соотнося каждому входному слову соответствующее ему выходное, получим искомое отображение, которое и является
автоматным отоб-
ражением, или автоматным оператором. Если результатом применения оператора к слову x
будет выходное слово y, то это обозначается так:
S(q
1
,x)=y или
S(x)=y.
Автоматное отображение можно определить и индуктивно:
− S(q
i
,
x
j
)=λ(
q
i
,
x
j
); (2.1.4)
− S(q
i
,x
x
j
)=
S(q
i
,x) λ(δ(
q
i
,x),
x
j
). (2.1.5)
Автоматное отображение обладает двумя свойствами, непосредствен- но следующими из определения:
1) слова x и y
=S(x) имеют одинаковую длину;
2) если x
=x
1
x
2
и
S(x
1
x
2
)=y
1
y
2
, где x
1
=y
1
=i,то S(x
1
)=y
1
. Иначе го- воря, образ отрезка длины
i равен отрезку образа той же длины.
Свойство второе означает, что автоматные операторы – операторы без предвосхищения, то есть операторы, которые перерабатывают слово сле- ва направо, не «заглядывая» вперед.
Эти два свойства были бы достаточными для автоматного отображе- ния, если бы речь шла о бесконечных автоматах, то есть автоматах с бес- конечным числом состояний. Для конечных автоматов этих условий, как мы дальше увидим, недостаточно.
Таким образом, одна из интерпретаций абстрактного автомата – это некоторое цифровое вычислительное, управляющее или преобразова- тельное устройство. Входная буква – это входной сигнал (комбинация сигналов на всех входах устройства), входное слово – последователь- ность входных сигналов, поступающих в дискретные моменты времени
t=1,2,3,… Выходное слово – последовательность выходных сигналов, выдаваемых автоматом, внутреннее состояние автомата – комбинация состояний запоминающих элементов устройства.
Такая интерпретация, безусловно, верна, но она не требуется, ни для определения автомата, ни для построения соответствующей теории ко-

41 нечных автоматов. Все, что действительно важно в абстрактной теории автоматов – это работа со словами при конечной памяти.
2.1.2. Задание автоматов
Поскольку функции δ и λ определены на конечных множествах, то их можно задать таблицами. Обычно две таблицы (для функции δ
и для функции λ) сводят в одну таблицу δ
×λ:Q×X→Q×Y и называют такую таблицу
автоматной таблицей, или таблицей переходов автомата. В этой таблице на пересечении столбца с входной буквой
x
i
и строки с со- стоянием
q
j
стоит пара − состояние
q
l
, в которое переходит автомат из состояния
q
j по входной букве
x
i
,
и выходная буква y
k
, которая при этом выдается автоматом.
Часто вместо автоматной таблицы для задания автомата используют так называемую
матрицу соединений автомата. Это матрица n×n, стро- ки и столбцы которой соответствуют различным состояниям автомата.
На пересечении
q
i
-й строки и
q
j
-го столбца стоит буква (или дизъюнкция букв) входного алфавита
x
l
∈X, вызывающая переход автомата из состоя- ния
q
i
в состояние
q
j
, и в скобках (можно через запятую, тире или слеш) – буква (или дизъюнкция букв) выходного алфавита
y
k
∈Y, которая появля- ется при этом на выходе автомата. Если ни одна из букв входного алфа- вита не переводит состояние
q
i в
q
j
, то ставится прочерк или ноль. В лю- бой строке каждая буква входного алфавита встречается не более одного раза (условие однозначности переходов).
Еще один способ задания автоматов – ориентированный мультиграф, называемый
графом переходов, или диаграммой переходов. Вершины графа переходов соответствуют состояниям автомата. Если δ(
q
i
,
x
j
)=
q
k
и
λ(q
i
,
x
j
)=
y
l
, то из вершины
q
i
в вершину
q
j ведет ребро, на котором напи- саны пара
x
j
,
y
l
. Для любого графа переходов выполняются следующие условия корректности: а) для любой входной буквы
x
j
имеется ребро, выходящее из
q
i
, на ко- тором написано
x
j
(условие полноты); б) любая буква
x
j
встречается только на одном ребре, выходящем из вершины
q
i
(условие непротиворечивости, или детерминированности).
На графе переходов наглядно представимы все функции, определяе- мые формулами (2.1.1) − (2.1.5). Если зафиксирована вершина
q
i
, то вся- кое слово
1 2
i
i
ik
x x
x
=
x
однозначно определяет путь длины k из этой вершины (обозначим его
q
i,
x), на
k ребрах которого написаны
1 2
i
i
ik
x x
x .

42
Поэтому δ(
q
i
,x)
− это последняя вершина пути q
i,
x; λ(
q
i,
x)
−выходная буква, написанная на последнем ребре пути
q
i,
x, а отображение
S(q
i,
x)
−
слово, образованное выходными буквами на
k ребрах пути q
i,
x
.
Пример 2.1.
Пусть автомат задан своей автоматной таблицей:
Т а б л и ц а 2 . 1
q\x
x
1
x
2 1
2,
y
1 3,
y
3 2
2,
y
2 3,
y
1 3
1,
y
1 2,
y
2
Здесь, и в дальнейшем, если это не вызовет разночтений, внутренние состояния обозначены своими индексами, т.е. алфавит состояний – это
{
}
1, 2,3
Q =
. Входной алфавит автомата
{
}
1 2
,
X
x x
=
, выходной алфавит
{
}
1 2
3
, ,
Y
y y y
=
Матрица соединений данного автомата приведена ниже:
Т а б л и ц а 2 . 2
q\q
1 2
3 1
0
x
1
,
y
1
x
2
,
y
3 2
0
x
1
,
y
2
x
2
,
y
1 3
x
1
,
y
1
x
2
,
y
2 0
На рис. 2.1 представлен граф (состояний) автомата.
Если на вход автомата, находящегося в состоянии 1, поступит, напри- мер, слово
1 2 2 1 2 2
x x x x x x
=
x
, то на выходе появится слово
1 1 2 2 1 2
y y y y y y
=
y
, а автомат перейдет в состояние 2.

43
Пример 2.2.
Граф, представленный на рис. 2.2, нельзя интерпретиро- вать как некоторый автомат, поскольку в этом графе нарушено условие автоматности: из вершины 2 выходят два ребра с одной буквой
а.
2.2 Виды автоматов и их свойства
Дадим несколько определений, которые понадобятся для дальнейшего изложения.
Состояние
q
j
называется достижимым из состояния q
i
, если суще- ствует входное слово x, такое, что
( , )
i
j
q
q
δ
=
x
. Автомат называется
силь-
но связанным, если из любого его состояния достижимо любое другое состояние.
1 3
2
x
2
,
y
3
x
1
,
y
1
x
2
,
y
1
x
1
,
y
1
x
2
,y
2
x
1
,y
2
Рис 2.1. Переходной граф состояний
3 1
2
c
a
a
b
a
Рис. 2.2. Граф, не являющийся автоматом

44
2.2.1. Автономные автоматы
Автомат называется
автономным по входу, если его входной алфавит состоит из одной буквы:
X={x}. Все входные слова у такого автомата имеют вид
xx…x.
Теорема 2.2.1
. Любое достаточно длинное выходное слово автоном- ного по входу автомата с
n состояниями является периодическим (воз- можно с предпериодом), причем длины периода и предпериода не пре- восходят
n. Оно имеет вид
1
σωω ωω ,где
1 0
,1
,
n
n
≤ σ ≤
≤ ω ≤
ω − начальный отрезок
ω .
Доказательство.
Так как в графе автономного по входу автомата из каждой вершины выходит одно ребро, то его сильно связанные подграфы могут быть только простыми циклами, из которых нет выходных ребер.
Поэтому в компоненте связности может быть только один цикл. Осталь- ные подграфы компоненты связности – это деревья, подвешенные к цик- лу и ориентированные в его сторону. Что и требовалось доказать.
Пример 2.3.
Автомат задан автоматной таблицей:
Т а б л и ц а 2 . 3
q
x
1 3,0 2
4,0 3
4,0 4
7,0 5
4,2 6
5,0 7
6,1
Граф автомата приведен на рис. 2.3. Входная буква на ребрах графа не показана.

45
Пусть автомат первоначально находится в состоянии 2, и на вход по- ступает слово
xxxxxxxxxxx. На выходе будет слово 00102010201, где пред- период
0
σ = , период =0102
ω
, начальный отрезок
1 01
ω =
Из произвольного автомата с входным алфавитом
X={x
1
,
…x
m
} может быть построено
m различных автономных по входу автоматов исключе- нием из графа переходов автомата всех ребер, кроме ребер с выбранной буквой
x
i
(
i=1,…, m).
Аналогично, автомат называется автономным по выходу, если его вы- ходной алфавит состоит из одной буквы
Y={y}. Автономный по выходу автомат получается из произвольного автомата с выходным алфавитом
{
}
1 2
, ,...
k
Y
y y
y
=
исключением из графа переходов ребер со всеми выход- ными буквами кроме выбранной буквы
i
y .
Пример 2.4.
Возьмем автомат из примера 2.1. Его автоматная таблица приведена ниже:
q\x
x
1
x
2 1
2,
y
1 3,
y
3 2
2,
y
2 3,
y
1 3
1,
y
1 2,
y
2
Таблица автономного автомата по входной букве, например
x
2
, полу- чится удалением всех столбцов, кроме столбца с буквой
x
2
:
q\x
x
2 1
3,
y
3 2
3,
y
1 3
2,
y
2 1
2 4
7 6
5 3
0 0
0 0
1 0
2
Рис. 2.3. Граф автономного автомата

46
Таблица автономного автомата по выходной букве, например
y
1
, по- лучится удалением всех элементов исходной таблицы, кроме элементов с буквой
y
1
:
q\x
x
1
x
2 1
2,
y
1
-
2
-
3,
y
1 3
1,
y
1
-
2.2.2. Автоматы синхронные и асинхронные
В синхронных автоматах переход из одного состояния в другое осу- ществляется через равные промежутки времени, задаваемые в реальных устройствах генератором тактовых импульсов. Другими словами, син- хронный автомат реагирует на каждую букву входного алфавита.
В асинхронном автомате его внутреннее состояние может меняться только при изменении входного состояния. В результате этого изменения автомат всегда приходит в конечном итоге в некоторое устойчивое пол- ное состояние
1
, т. е. в такое полное состояние, в котором автомат остает- ся до тех пор, пока не изменится его входное состояние.
Полагают также, что новое изменение входа не может произойти до того, как автомат перейдет в устойчивое полное состояние.
В итоге моменты перехода асинхронного автомата из состояния в со- стояние зависят от значения входа. Понятно, что при этом теряет смысл рассмотрение входных слов, содержащих одинаковые соседние буквы.
Сформулированные для асинхронного автомата условия налагают не- которые ограничения на таблицу переходов
i j
δ .
Чтобы было понятнее, рассмотрим вначале усиленный вариант этих условий, когда любое полное состояние автомата связано с некоторым устойчивым состоянием прямым, непосредственным переходом. Это означает, что если некоторый элемент
i j
δ автоматной таблицы имеет значение
q
k
, то это же значение должен иметь и элемент
k j
δ .
Такому требованию удовлетворяет, например, следующая таблица пе- реходов:
1
Полное состояние – это совокупность входного и внутреннего состояний.

47
Табли ца 2.4
q\x
x
1
x
2
x
3
x
4 1
1
1
1
5 2
1
2
2
2
3
3
2 4
5 4
3 2
4
5 5
3
5
4
5
Жирным шрифтом выделены элементы, соответствующие устойчи- вым полным состояниям.
В общем виде эти условия формулируются так: для любого элемента
δ
ij
таблицы переходов должна выполняться цепочка равенств
1 2
1
,
, ...,
i j
k j
k j
p
p
k
k
k
δ =
δ =
δ
=
Это означает, что любое полное состояние
( , )
i
j
q x асинхронного ав- томата должно быть связано цепочкой переходов с некоторым устойчи- вым полным состоянием
(
, )
k
j
p
q
x .
На таблицу выходов
ij
λ
асинхронного автомата каких-либо ограни- чений не налагают.
2.2.3.
Автоматы Мили и автоматы Мура
Общее определение автомата, данное в разделе 2.1, задает так называ- емый
автомат Мили. Характерной особенностью автомата Мили являет- ся то, что значение его выхода зависит от полного состояния, то есть как от внутреннего, так и от входного состояний. Другими словами, функция выхода
λ
является двуместной функцией ( )
( (
1), ( )).
y t
q t
x t
= λ
−
В случае если функция выхода зависит только от внутреннего состоя- ния, но не от входа, получаем автомат, носящий название
автомата Му-
ра. Для автомата Мура для любых q, x
i и
x
j
выполняется условие
( , )
( , )
i
j
q x
q x
λ
= λ
, т. е. функция выхода одноместная. Часто ее в этом слу- чае обозначают буквой
µ
и называют
функцией отметок, так как она каж- дое состояние помечает вполне однозначно буквами выходного алфавита.

48
Для автомата Мура таблица выходов вырождается в один столбец, а автоматная таблица записывается с лишним столбцом. Матрица соедине- ний также содержит лишний столбец.
Возможности этих двух видов автоматов совпадают, то есть для лю- бого автомата Мили существует эквивалентный ему автомат Мура (и наоборот). Это утверждение можно сформулировать в виде теоремы.
Теорема 2.2.2
. Для произвольного автомата Мили
{
}
{
}
1 2
1 2
( , , , , ),
, ,...
,
, ,...
m
n
S
X Q Y
X
x x
x
Q
q q
q
=
δ λ
=
=
, существует эквивалентный ему автомат Мура
M
M
M
M
M
(
,
,
,
, )
S
X Q Y
=
δ µ
Он может быть построен следующим образом: входной и выходной алфавиты исходного автомата Мили и эквивалентного автомата Мура совпадают
X
M
=
X, Y
M
=
Y. Алфавит состояний Q
M содержит
m·n+n состоя- ний:
m·n состояний
i j
q
(
i=1,…n, j=1,…m), соответствующих парам
( , )
i
j
q x
автомата
S и n состояний
0
i
q (i=1,…n). Функция
М
δ
определяется так:
M
0
( , )
i
k
i k
q x
q
δ
=
(
i=1,…n),
M
(
, )
i j
k
l k
q x
q
δ
=
, где индекс
l определяется функцией перехода автомата
S:
( , )
i
j
l
q x
q
δ
=
. Функция отметок
0
(
)
i
q
µ
−
не определена, а для остальных состояний
(
)
( , )
i j
i
j
q
q x
µ
= λ
. Состояние
0
i
q
(
i=1,…n) автомата S
M отождествляется с начальным состоянием
q
i
автомата
S (если задан инициальный автомат).
Доказательство теоремы заключается в том, чтобы показать равенство автоматных отображений
M
0
( , )
(
, )
i
i
S q
S q
=