Алгоритм Дейкстры-Прима

a. Нарисуем города – вершины графа, найдем число необходимых ребер: 6-1 = 5
b. Выберем ребра, имеющие минимальный вес 1: 1-4, 2-5, 4-5, включаем их в граф
c. Опять выберем ребра с минимальным весом 2: 1-3, 1-6, 3-5, ребро 3-5 образует цикл, поэтому в граф его включать не будем. Т.к. количество ребер равно 5, то минимальное остовное дерево построено.

Вес минимального остовного дерева равен: 1 + 1 + 1 + 2 + 2 = 7.

3) Найти кратчайшие пути от вершины 1 до всех остальных вершин графа, изображенного на рис. 4.16, по алгоритму Дейкстры.

Рис. 4.16

Решение:

a) Т.к. исходная вершина 1, то длина пути 1-1 = 0 – постоянная метка (обозначили +). всем остальным вершинам присвоим метки ¥.

Таблица 4.2

b) Из вершины 1 выходят дуги в вершины 2, 4, 5. Пересчитываем метки этих вершин и заполняем следующую строку:

d(2) = min (¥; 0 + 3) = 3

d (4) = min (¥; 0 + 2) = 2

d (5) = min (¥; 0 + 8) = 8

В качестве постоянной выберем вершину с меньшей меткой 2 – вершина 4.

Таблица 4.3

c) Из вершины 4 выходят дуги в вершины 2, 5. Пересчитываем метки этих вершин и заполняем следующую строку:

d (2) = min (3; 2 + 7) = 3

d (5) = min (8; 2 + 5) = 7

В качестве постоянной выберем вершину с меньшей меткой 3 – вершина 2.

Таблица 4.4

d) Из вершины 2 выходят дуги в вершины 3, 5, 6. Пересчитываем метки этих вершин и заполняем следующую строку:

d (3) = min (¥; 3 + 6) = 9

d (5) = min (7; 3 + 1) = 4

d (6) = min (¥; 3 + 1) = 4

Так как метки вершин 5 и 6 одинаковы, то в качестве постоянной вершину выберем произвольно – вершина 5.

Таблица 4.5

e) Из вершины 5 выходят дуги в вершины 3, 6. Пересчитываем метки этих вершин и заполняем следующую строку:

d (3) = min (9; 4 + 5) = 9

d (6) = min (4; 4 + 3) = 4

В качестве постоянной выберем вершину с меньшей меткой 4 – вершина 6.

Таблица 4.6

f) Из вершины 6 выходит дуга в вершину 3. Пересчитываем метку этой вершины и заполняем последнюю строку:

d (3) = min (9; 4 + 4) = 8

В качестве постоянной выберем вершину с меньшей меткой 8 – вершина 3. На этом расчет окончен, найдены кратчайшие пути до всех вершин графа из точки 1.

Таблица 4.7

4) Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, изображенного на рис. 4.17, по алгоритму Беллмана.

a). Для построения кратчайших путей графа удобно воспользоваться таблицей: в столбцах записаны вершины графа, в строках - . Первый столбец соответствует первой вершине s и содержит только 0.

Рис. 4.17

b). На первом шаге находятся пути одной дуги от вершины 1 до вершин 2,4,5.

c). Занесем в строку 1, если пути нет, то ставим ¥. Пути состоящие более чем из 2-х дуг следует искать только для вершин, в которые входят дуги, выходящие из вершин 2,4,5:

из 2 – в 3,4,5,6

из 4 – в 2,5,7,8

из 5 – в 2,3,4,6,7,9

d). Уменьшились длины путей до вершин: 2,3,6,7,8,9. А значит, имеет смысл искать более короткие дуги до тех вершин графа, в которые входят дуги из перечисленных вершин

из 2 – в 3,4,5,6

из 3 – в 2,5,6

из 6 – в 3,5,8,9

из 7 – в 4,5,8

из 8 – в 4,5,6,7,9

из 9 – в 5,6

.

e). Уменьшились длины путей до вершин: 3,5,6,8,9. А значит, имеет смысл искать более короткие дуги до тех вершин графа, в которые входят дуги из перечисленных вершин. И т.д.

f). При заполнении 7-й строки обнаруживаем, что значения строки повторяют 6-ю строку, а значит, алгоритм закончил свою работу.

Составим дерево кратчайших путей:

- корень – вершина 1

- длина кратчайшего пути до вершины 4 была найдена уже на первом шаге – включаем дугу 1-4 в дерево.

- во второй строке стоят кратчайшие пути до вершин 2 и 7, а из диаграммы видно, что эти пути идут через вершину 4.

- в третьей строке стоит кратчайший путь до вершины 6 (содержит три дуги), а из диаграммы видно, что этот пути идет через вершины 4 и 2, и т.д.

Таблица 4.8

Дерево:

Рис. 4.18

5) Отыскать все гамильтоновы циклы графа, изображенного на рис. 4.19.

Рис. 4.19

Решение:

a). Выберем вершину 1 за начальную точку.

b). Выпишем наборы, состоящие из начальной вершины и смежной с ней: 1-2, 1-3, 1-4.

c). Выпишем наборы, состоящие из наборов п. 2 и смежных с ними вершин: 1-2-5, 1-3-4, 1-3-5, 1-4-3, 1-4-5.

d). Выпишем наборы, состоящие из наборов п. 3 и смежных с ними вершин: 1-2-5-3, 1-2-5-4, 1-3-4-5, 1-3-5-4, 1-3-5-2, 1-4-3-5, 1-4-5-3, 1-4-5-2.

e). Выпишем наборы, состоящие из наборов п. 4 и смежных с ними вершин: 1-2-5-3-4, 1-2-5-4-3, 1-3-4-5-2, 1-3-5-4, 1-3-5-2, 1-4-3-5-2, 1-4-5-3, 1-4-5-2, наборы 1-3-5-4, 1-3-5-2, 1-4-5-3, 1-4-5-2 не включают пятую вершину, а значит, не образуют гамильтонова цикла.

f). Замкнем цикл - 1-2-5-3-4-1, 1-2-5-4-3-1, 1-3-4-5-2-1, 1-4-3-5-2-1.

Рис. 4.20 – Дерево гамильтоновых циклов

6) Проверить является ли граф, изображенный на рис. 4.21, эйлеровым, полуэйлеровым или не эйлеровым, в первых двух случаях построить эйлеров цикл или эйлеров путь соответственно.

Рис. 4.21

Решение:

По теореме Эйлера проверим четность степеней вершин графа (посчитаем количество вершин, смежных с данной):

Все степени вершин являются четными (таблица 4.9), значит, граф является эйлеровым. Отыщем эйлеров цикл в графе по алгоритму Флёри, за начало пути возьмем вершину 1.

Таблица 4.9

1) Убираем ребро 1-2 2) Убираем ребро 2-3

3) Убираем ребро 3-4 и вершину 3 4) Убираем ребро 4-6

5) Убираем ребро 6-5 и вершину 6 6) Убираем ребро 5-4

7) Убираем ребро 4-2 и вершину 4 8) Убираем ребро 2-5

9) Убираем ребро 5-7 и вершину 5, вернулись в исходную вершину 1.

10) Эйлеров цикл: 1-2-3-4-6-5-4-2-5-7-1 – граф – эйлеров.

Упражнения

1) Для графа построить матрицу смежности:

1.1	1.2
1.3	1.4
1.5	1.6
1.7	1.8
1.9

2) Для графа построить матрицу достижимости

2.1	2.2
2.3	2.4
2.5	2.6
2.7	2.8
2.9

3) Для графа построить матрицу инциденций

3.1	3.2
3.3	3.4
3.5	3.6
3.7	3.8
3.9

4) Для графов, приведенных на рис. 1-9 выполнить задания:

a). С помощью алгоритма Дейкстры-Прима отыскать минимальное остовное дерево графа.

b). С помощью алгоритма Дейкстры построить дерево кратчайших путей графа.

c). С помощью алгоритма Беллмана построить дерево кратчайших путей графа.

d). Отыскать все гамильтоновы пути в графе, если такие есть.

e). Проверить, является ли граф эйлеровым, полуэйлеровым или не эйлеровым, отыскать эйлеров цикл и эйлеров путь, если такие есть.

4.1	4.2
4.3	4.4
4.5	4.6
4.7	4.8
4.9

Вопросы для самоконтроля и повторения

1. Что такое граф? Ориентированный граф?

2. Перечислите основные понятия, связанные с графами

3. Перечислите способы задания графов

4. Что такое матрица смежности, инцидентности, достижимости графа?

5. Какой граф называется связным?

6. Перечислите основные операции над графами.

7. Что такое эйлеров граф? Гамильтонов граф?

8. Перечислите способы построения дерева кратчайших путей графа.

5. Теория кодирования

5.1. Основные понятия теории кодирования

Код – правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита; знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита.

Кодирование – перевод информации, представленной посредством первичного алфавита, в последовательность кодов.

Декодирование – операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.

Алфавитное кодирование – это представление информации в стандартной форме, при которой элементарным синтаксическим единицам языка сообщений (буквам алфавита) последовательно сопоставляются кодовые комбинации символов из некоторого заданного алфавита.

Пусть задан алфавит сообщений А ={a₁, a₂,…a_n} состоящий из вечного числа букв – конечное множество. Конечная последовательность букв из А: a = a_i1, a _i2,…a _ik называется словом в алфавите А, а число k - длиной слова a; если k = 0, то слово называют пустым и обозначают Ù.

Множество всех непустых слов конечной длины в алфавите А обозначим А*.

Если S Î A* (S – подмножество множества А*), то слова из S являются сообщениями, а объект, порождающий слова из S – источником сообщений. Источником сообщений может быть человек, автомат и т.д.

Пусть, кроме алфавита А, задан еще алфавит В = {b₁, b₂,… b_m}. Зададим отображение f, которое каждому слову a Î S ставит в соответствие слово b Î В*, где В* — множество всех непустых слов конечной длины в алфавите В.

Слово b будем называть кодом сообщения a, а процесс перехода от слова a к слову b – кодированием.

5.2. Проблема взаимной однозначности

Одним из основных вопросов в кодировании является проблема взаимной однозначности, т.е. возможность по коду b сообщения a однозначно восстановить сообщение a.

Достаточный признак взаимной однозначности алфавитного кодирования:

Если b = b'b", то b' называется началом, или префиксом, слова b, b" — окончанием, или постфиксом, слова b. Если b' ¹ Ù, то b' называется собственным началом. Если b"¹ Ù, то b" называется собственным окончанием слова b. Схема алфавитного кодирования обладает свойством префикса, если ни один элементарный код не является префиксом другого элементарного кода. Если схема S алфавитного кодирования обладает свойством префикса, то алфавитное кодирование взаимно однозначно.

Условие префиксности не является необходимым, т.е. алфавитное кодирование может быть взаимно-однозначным, но не обладать свойством префиксности.

Слово b_inb_in-1.. b_i1 будем называть обратным к слову b = b₁b₂… b_in и обозначать b^-1. Схему кодирования, полученную из схемы кодирования S заменой каждого элементарного кода b_i на b_i^-1, будем называть обратной к схеме S и обозначать S^-1. Тогда: если схема S или схема S^-1 обладает свойством префикса, то тогда алфавитное кодирование, определяемое схемой S(S^-1), будет взаимно однозначным.

Общий критерий взаимной однозначности.

Нетривиальное разложение: представим слово b в виде:

b = b'b₁b₂… b_inb",

где слово b' не может оканчиваться на элементарный код, а b" не может начинаться с элементарного кода. Причем одно из слов b', b", b₁b₂… b_in может быть пробелом - Ù. Для определения однозначности алгоритма кодирования необходимо выполнить действия в соответствии с алгоритмом:

1). Для каждого элементарного кода выписываем все нетривиальные разложения.

2). Выписываем множество M₁, состоящее из слов b', являющихся началом нетривиальных разложений.

3). Выписываем множество M₂, состоящее из слов b", являющихся окончаниями нетривиальных разложений.

4). Выписываем множество М = М₁ Ç М₂ È {Ù}, т.е. множество слов, являющихся как началом, так и окончанием нетривиального разложения и пробел.

5). Выписываем все разложения, связанные с множеством M, т.е.

b = b'b₁b₂… b_inb",

где b', b" Î М, причем n может быть равно 0 (заменяется Ù).

6). По полученным разложениям строится ориентированный граф, следующим образом: вершины графа отождествляются с элементами множества М, пара вершин b' и b" соединяются ребрами только в том случае, если существует разложение b'b₁b₂… b_inb", ребру приписывается значение b₁b₂… b_in.

7). По полученному графу легко проверить, обладает ли схема кодирования однозначностью.

Теорема А.А. Маркова: алфавитное кодирование со схемой S не обладает свойством взаимной однозначности тогда и только тогда, когда граф содержит ориентированный цикл, проходящий через вершину Ù.

5.3. Коды Хемминга

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

Число дополнительных разрядов для построения кодов Хемминга нужно выбрать так, чтобы их хватило для кодирования перечисленных l +1 случаев. Следовательно, необходимо, чтобы выполнялись условия:

2^k >= l + 1, 2^m <= 2^l / l + 1.

Число l называется длиной кода Хемминга, m – число информационных символов, k – число контрольных символов – наименьшее целое число, удовлетворяющее условию 2^k >= k + m + 1.

Алгоритм построения кода Хемминга для кода a₁a₂…a_m:

1) Определим длину кода Хемминга:

m – число информационных символов,

2^k >= k + m +1 – число контрольных символов,

l = m + k – длина кода Хемминга.

2) Представим каждое число i из множества L = {1, 2, … l} в виде k-разрядного числа t = V_k-1V_k-2..V₀ . Результат запишем в виде таблицы:

Таблица 5.1

3) Разобьем множество L на подмножества следующим образом:

L ₀ = {i Î L ₀: V₀ = 1}

L ₁ = {i Î L ₁: V₁ = 1}

L ₂ = {i Î L ₂: V₂ = 1}

L ₃ = {i Î L ₃: V₃ = 1}

….

L _k-1 = {i Î L _k-1: V _k-1 = 1}

4) Первые элементы (их ровно k) являются степенью числа 2, они определяют номера контрольных разрядов кода Хемминга:

b₁ b₂ b₄ b₈…

5) Остальные разряды являются информационными, заполняются исходного сообщения по порядку:

b₃ = a₁, b₅ = a₂, b₆ = a₃, …, b_l = a_m.

6) Контрольные разряды заполняются следующим образом:

b₁ = Å b_j, b_j Î L ₀, j ¹ 1,

b₂ = Å b_j, b_j Î L ₁, j ¹ 2,

b₄ = Å b_j, b_j Î L ₂, j ¹ 4,

b₈ = Å b_j, b_j Î L ₃, j ¹ 8.

Обнаружение ошибки в кодах Хемминга

Если при передаче по каналу связи получили сообщение b¢, и известно что при передаче произошла одна ошибка в неизвестном разряде, то можно найти этот разряд, обозначим его t. Для его нахождения представим t в виде двоичного числа: t = V¢_k-1V¢_k-2.. V¢₀.

Найдем эти числа V¢ по формулам:

V¢₀ = Å b¢_j, b¢ _j Î L ₀,

V¢₁ = Å b¢ _j , b¢ _j Î L ₁,

V¢₂ = Å b¢ _j, b¢ _j Î L ₂,

……………………..

V¢_k-1 = Å b¢ _j, b¢ _j Î L ₃.

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

Примеры решения задач

1) Выяснить, является ли код однозначно декодируемым?

С(S) = {b₁, b₁b₂, b₃b₁}

Решение

Код S не является префиксным, кроме того и код S^-1 = {b₁, b₂b₁, b₁b₃} не является префиксным. Однако по коду можно однозначно восстановить исходное слово. Алгоритм следующий:

a). В кодовом слове находим все буквы b₂ и выделяем пары b₁b₂,

b). В кодовом слове находим все буквы b₃ и выделяем пары b₃b₁,

c). Заменяют найденные пары символами исходного алфавита, и определяются оставшиеся буквы b₁.

2) Алфавитное кодирование задано схемой S в виде таблицы

Таблица 5.2

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

Решение

a) Для каждого элементарного кода выписываем все нетривиальные разложения:

b₁ = (b₁)(b₂)

b₂ = (b₁)(b₃b₂) = (b₁b₃)(b₂)

b₃ = (b₂)(b₃)

b₄ = (b₁)(b₂ b₁b₃) = (b₁b₂)(b₁b₃) = (b₁b₂ b₁)( b₃)

b₅ = (b₂)(b₁b₂ b₂ b₃) = (b₂ b₁)(b₂ b₂ b₃) = (b₂ b₁b₂)(b₂ b₃) = (b₂ b₁b₂ b₂)(b₃)

b) Выписываем множество M₁, состоящее из слов b', являющихся началом нетривиальных разложений.

М₁ = {b₁, b₁b₃, b₂, b₁b₂, b₁b₂ b₁, b₂ b₁, b₂ b₁b₂, b₂ b₁b₂ b₂}

c) Выписываем множество M₁, состоящее из слов b", являющихся окончаниями нетривиальных разложений

M₂ = {b₂, b₃b₂, b₃, b₂ b₁b₃, b₁b₃, b₁b₂ b₂ b₃, b₂ b₂ b₃, b₂ b₃}

d) Выписываем множество М = М₁ Ç М₂ È {Ù}, т.е. множество слов, являющихся как началом, так и окончанием нетривиального разложения и пробел.

M = {b₂, b₁b₃, Ù}

e) Выписываем все разложения, связанные с множеством M, т.е.

b = b'b₁b₂… b_inb", где b', b" Î М, причем n может быть равно 0 (заменяется Ù).

b₂ = (b₁b₃)Ù(b₂)

b₄ (b₁b₂)(b₁b₃) = Ù b₁ b₁b₃

b₅ = (b₂)(b₁b₂)(b₂ b₃) =(b₂) b₁b₃Ù

f) По полученным разложениям строится ориентированный граф, следующим образом: вершины графа отождествляются с элементами множества М, пара вершин b' и b" соединяются ребрами только в том случае, если существует разложение b'b₁b₂… b_inb", ребру приписывается значение b₁b₂… b_in.

Рис. 5.1

g) По полученному графу легко проверить, обладает ли схема кодирования однозначностью. Т.к. в графе есть цикл, проходящий через Ù. то взаимно-однозначного кодирования нет.

h) Найдем слово. декодируемое неоднозначно: начнем выписывать последовательно слова. присвоенные ребрам и вершинам. начиная с пробела и заканчивая пробелом:

b₁b₂ b₁b₃ b₂ b₁b₂ b₂b₃

b1 = (b₁b₂)(b₁b₃b₂)(b₁b₂)(b₂b₃) ® a1 = a₁a₂a₁a₃

b2 = (b₁b₂b₁b₃)(b₂b₁b₂b₂b₃) ® a2 = a₄a₅

3) Пусть задано сообщение a = 1011011 = a₁a₂a₃a₄a₅a₆a₇. Для этого сообщения необходимо построить код Хемминга.

Решение

a). Определим длину кода Хемминга:

m = 7, 2^k >= k + 10, k = 4, l = 11.

b). Представим каждое число i из множества L = {1, 2, … l} в виде k-разрядного числа t = V_k-1V_k-2..V₀ . Результат запишем в виде таблицы 5.3.

с). Разобьем множество L на подмножества следующим образом:

L₀ = {1, 3, 5, 7, 9, 11}

L₁ = {2, 3, 6, 7, 10, 11}

L₂ = {4, 5, 6, 7}

L₃ = {8, 9, 10, 11}

Таблица 5.3

d). Первые элементы (их ровно k) являются степенью числа 2, они определяют номера контрольных разрядов кода Хемминга:

b₁ b₂ b₄ b₈

e). Остальные разряды являются информационными, заполняются исходного сообщения по порядку:

b₃ = 1, b₅ = 0, b₆ = 1, b₇ = 1, b₉ = 0, b₁₀ = 1, b₁₁ = 1.

f). Контрольные разряды заполняются следующим образом:

b₁ = b₃ Å b₅ Å b₇ Å b₉ Å b₁₁ = 1 Å 0 Å 1 Å 0 Å 1 = 1,

b₂ = b₃ Å b₆ Å b₇ Å b₁₀ Å b₁₁ = 1 Å 1 Å 1 Å 1 Å 1 = 1,

b₄ = b₅ Å b₆ Å b₇ = 0 Å 1 Å 1 = 0,

b₈ = b₉ Å b₁₀ Å b₁₁ = 0 Å 1 Å 1 = 0.

Окончательное решение для слова a = 1011011: b = 11100110011.

4) Пусть вместо кода b = 11100110011, на приемник пришло слово b¢ = 10100110011. Найти, в каком разряде произошла ошибка, и исправить ее.

Решение

Найдем числа V¢:

V¢₀ = b₁ Å b₃ Å b₅ Å b₇ Å b₉ Å b₁₁ Å b₁₃ = 1 Å 1 Å 0 Å 1 Å 0 Å 1 = 0,

V¢₁ = b₂ Å b₃ Å b₆ Å b₇ Å b₁₀ Å b₁₁ = 0 Å 1 Å 1 Å 1 Å 1 Å 1 = 1,

V¢₂ = b₄ Å b₅ Å b₆ Å b₇ = 0 Å 0 Å 1 Å 1 = 0,

V¢₃ = b₈ Å b₉ Å b₁₀ Å b₁₁ =0 Å 0 Å 1 Å 1 = 0.

t = 0100, следовательно ошибка произошла в разряде 2, исправим символ в этом разряде на противоположный.

Исходный код b = 11100110011.

Упражнения

Таблица 5.4

1) Закодировать слово с помощью азбуки Морзе, сопоставляя буквам коды из таблицы 5.4:

1.1 слово

1.2 книга

1.3 музыка

1.4 физика

1.5 автобус

1.6 магазин

1.7 свойство

1.8 критерий

1.9 математика

1.10 университет

2) Закодировать двоичным алфавитом слова:

2.1 слово

2.2 книга

2.3 музыка

2.4 физика

2.5 автобус

2.6 магазин

2.7 свойство

2.8 критерий

2.9 математика

2.10 университет

3) Найти длину кода Хэмминга, если число символов сообщения равно m

3.1 m = 2

3.2 m = 3

3.3. m = 5

3.4 m = 7

3.5 m = 10

3.6 m = 12

3.7 m = 15

3.8 m = 22

3.9 m = 30

3.10 m = 57.

4) Построить код Хэмминга для сообщения a

4.1 a = 10001

4.2 a = 100111

4.3 a = 1101010

4.4 a = 10110100

4.5 a = 111001001

4.6 a = 0011000010

4.7 a = 11010110110

4.8 a = 100110101001

4.9 a = 1010101110110

4.10 a = 11011001001110

5) На приемник пришло сообщение b, известно, что ошибка произошла только в одном разряде. Восстановить исходное сообщение.

5.1 b = 10101

5.2 b = 100101

5.3 b = 1101110

5.4 b = 10111100

5.5 b = 101001001

5.6 b = 1011000010

5.7 b = 10010110110

5.8 b = 101110101001

5.9 b = 1010101010110

Вопросы для самоконтроля и повторения

1. В чем состоит процесс кодирования?

2. Что такое кодирование и декодирование?

3. Что такое алфавитное кодирование?

4. Укажите признаки взаимной однозначности кодирования.

5. Как строится двоичное кодирование?

6. Каковы свойства самокорректирующихся кодов?

7. Какие коды называются кодами Хемминга?

8. Опишите процесс кодирования Хемминга.

9. Опишите процесс декодирования Хемминга.

6. Теория автоматов

6.1. Основные понятия теории автоматов

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

Математической моделью реального конечного автомата является абстрактный автомат, который имеет один входной канал и один выходной канал.

Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y, d, l),

где

A = {a₀, a₁, a₂,..., a_n} – множество внутренних состояний автомата,

X = {x₁, x₂,…, x_m} – множество входных сигналов (входной алфавит),

х_i – буква входного алфавита,

Y = {y₁, y₂,…, y_k} – множество выходных сигналов (выходной алфавит),

d - функция переходов, определяющая состояние автомата a(t+1), в котором автомат будет находиться в момент времени (t+1), в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. a(t+1) = d [a(t), x(t)],

l - функция выходов, определяющая значение выходного сигнала y(t) в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. y(t) = l[a(t), x(t)].

Применяемые на практике автоматы принято разделять на два класса: автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать.

Закон функционирования автоматов Мили описывается следующей системой уравнений:

a(t + 1) = d[a(t), x(t)],

y(t) = l[a(t), x(t)],

t = 0,1,2,3…

Работа автоматов Мура задается следующими уравнениями:

a(t + 1) = d[a(t), x(t)] ,

y(t) = l[a(t)]

6.2. Способы задания конечного автомата

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l} , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l. При этом среди множества A = {a₀, a₁, …, a_n} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный, графический, задание с помощью булевых функций.

1). Табличный способ. При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Таблица переходов Таблица выходов

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца a_i и строки x_j в таблице переходов ставится состояние a_s = d[a_i, x_j], в которое автомат перейдет из состояния a_i под воздействием сигнала x_j; а в таблице выходов – соответствующий этому переходу выходной сигнал y_g = l[a_i, x_j].

Таблица 6.1

Совмещенная таблица переходов и выходов автомата Мили:

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

2). Графический способ задания автомата(задание автомата с помощью графа) – этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a_i и a_s соединяются дугой, направленной от a_i к a_s, если в автомате имеется переход из a_i в a_s, т.е. a_s = d(a_i, x_j). В автомате Мили дуга отмечается входным сигналом x_j, вызвавшим переход, и выходным сигналом y_g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.

3). Задание с помощью булевых функций – если автомат задан табличной функцией или диаграммой Мура, то возможно задание автомата с помощью булевых функций. Алгоритм задания следующий:

a. Находим числа k, r, s, удовлетворяющие условиям:

2^k-1 < m < 2^k

2^r-1 < n < 2^r

2^s-1 < p < 2^s

где m = |X|, n = |A|, p = |Y| - число символов множеств.

При этом видно, что k, r, s равны числу разрядов, в двоичном представлении чисел m, n, p.

b. Кодируем входные и выходные символы исходного автомата:

Каждому a_i Î А взаимно-однозначно ставим в соответствие двоичную последовательность длины r – двоичный код a (а) = a₁a₂..a_r. Аналогично и для каждого x и y: b (x) = b₁b₂..b_k, g (y) = g₁g₂…g_s.

c. Составляем следующую таблицу:

Таблица 6.2

Эта таблица содержит k + r + r + s столбцов и 2^k+1 строк.

d. Заполнение последних столбцов в таблице: для каждой пары (x_i, a_j) по таблице автомата находим d(x, a) = a’ и l (x, a) = y. Затем находим код a (а) = a₁’ a₂’..a _r’ и g(y) = g₁g₂…g_s.

Примеры решения задач

1). По таблицам Милли и Мура найти выходное слово при входном слове x₁x₂x₂x₂x₁

Таблица 6.3

Для автомата Милли:

a). Изначально автомат находится в состоянии a₀. При поступлении на вход первого символа x₁ автомат перейдет в состояние a₁ и на выходе будет символ y₁.

b). При поступлении на вход второго символа x₂ автомат находится уже в состоянии a₁, состояние изменится на a₀, а на выходе получим y₁, и т.д.

c). На выходе получим слово y₁y₁y₂y₂y₁.

Для автомата Мура:

a). Изначально автомат находится в состоянии a₀. При поступлении на вход первого символа x₁ автомат перейдет в состояние a₂ и на выходе будет символ y₂.

b). При поступлении на вход второго символа x₂ автомат находится уже в состоянии a₂, состояние изменится на a₄, а на выходе получим y₁, и т.д.

c). На выходе получим слово y₂y₁y₂y₁y₂.

2). Для приведенных в примере 1) таблиц Милли и Мура построить графы для задания автоматов.

Для автомата Милли:

a). Нарисуем четыре вершины графа, каждая из которых соответствует одному из состояний автомата.

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

Рис. 6.1

Для автомата Мура:

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

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

Рис. 6.2

3). Представить в виде конечного автомата элемент задержки.

Решение

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

Рис. 6.3

Предположим, что входной, и, следовательно, выходной алфавит есть: X{0,1}, Y{0,1}. Кроме того, А{0,1} – под состоянием элемента задержки в момент времени t понимается содержание элемента памяти в данный момент. Таким образом, а(t) = X(t – 1), Y(t) = а(t) = X(t – 1).

Зададим элемент задержки таблицей, где х₁ = 0, х₂ = 1, а₁ = 0, а₂ = 1.

d (x₁; a₁) = d (0; 0) = 0 l (x₁; a₁) = l (0; 0) = 0

d (x₁; a₂) = d (0; 1) = 0 l (x₁; a₂) = l (0; 1) = 1

d (x₂; a₁) = d (1; 0) = 1 l (x₂; a₁) = l (1; 0) = 0

d (x₂; a₂) = d (1; 1) = 1 l (x₂; a₂) = l (1; 1) = 1

Таблица 6.4

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

2^k-1 < m < 2^k,

2^r-1 < n < 2^r,

2^s-1 < p < 2^s,

где m = 2, n = 2, p = 2 - число символов множеств.

При этом видно, что k, r, s равны числу разрядов, в двоичном представлении чисел m, n, p: k = 1, r = 1, s = 1, k + r + r + s = 4, т.о. таблица истинности содержит четыре строки.

Таблица 6.5

4). Представить в виде конечного автомата двоичный сумматор последовательного действия.

Решение

Данный сумматор представляет собой устройство, осуществляющее сложение двух чисел в двоичной системе исчисления. На входы сумматора подаются числа х₁ и х₂, начиная с младших разрядов. На выходе формируется последовательность, соответствующая записи числа х₁ + х₂ в двоичной системе исчисления.

Рис. 6.4

Входной и выходной алфавит заданы однозначно: Х = {00, 01, 10, 11}, Y = {0, 1}. Множество состояний определяется значением переноса при сложении соответствующих разрядов чисел х₁ и х₂. Если при сложении некоторых разрядов образовался перенос, то будем считать, что сумматор перешел в состояние a₁. При отсутствии переноса будем считать, что сумматор находится в состоянии a₀.

Сумматор задается таблицей (если состояние а₀, то при комбинациях 00, 01, 10 – сумма будет 0 или 1, при 11 – сумма равна 10, есть перенос – состояние меняется на а₁; если состояние а₁ – то подразумеваем, что прошлым действием был перенос и 1 держим «в уме», теперь при сложении 00 будет на выходе 1 (с учетом 1 «в уме»), следующее состояние а₀ – переноса не было, при сложении 01 или 10, то с учетом единицы в уме получаем 10, наблюдаем перенос и состояние устанавливаем в а₁, на выходе 0, при сложении 11, то с учетом единицы в уме получаем 11, наблюдаем перенос и состояние устанавливаем в а₁, на выходе 1):

Таблица 6.6

Упражнения

1). По таблице Милли найти выходное слово при входном слове X

1.1 X = 10011011001

1.2 X = 01000111101

1.3 X = 01011010101

1.4 X = 01000001100

1.5 X = 11100111101

2). По таблице Милли найти выходное слово при входном слове X

2.1 X = 10011011001

2.2 X = 01000111101

2.3 X = 01011010101

2.4 X = 01000001100

2.5 <