Можно ли нарисовать картинки, не отрывая карандаша от бумаги и проводя каждую линию ровно один раз. Какие из них являются эйлеровыми графами.

0)	1)	2)
3)	4)	5)
6)	7)
8)	9)

3.5.2.

7)

Задайте граф геометрически и решите задачу:

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

0) не с него начал и не на нем закончил?

1) с него начал, но не на нем закончил?

2) с него начал и на нем закончил?

3) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

4) В стране Озерная 7 озер, соединенных между собой 10 непересекающимися каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

5) Можно ли построить 3 дома, вырыть 3 колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?

6) Можно ли составить решетку размером 4´4 (длина стороны клетки = 1):

а) из 5 ломаных длины 8? б) из 8 ломаных длины 5?

7) В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?

8) В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из N авиакомпаний, причем из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из любого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт N- 1рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по-прежнему из любого города можно долететь до любого другого.

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

3.5.3. Граф задан геометрически. Выпишите гамильтонов цикл у данного графа, если он есть:

0) Решение:	1) Решение:
2) Решение:	3) Решение:
4) Решение:	5) Решение:
6) Решение:	7) Решение:
8) Решение:	9) Решение:

Глава 4. Автоматы

Система A=(X;Q;Y;j;y) называется конечным автоматом,
где

X = {a1,…,am}	- входной алфавит с входными сигналами,
Q = {q1,…,qn}	- множество состояний,
Y = {b1,…,bp}	- выходной алфавит с выходными сигналами,
j: X ´ Q ® Q	- функция переходов, т.е. j(x, q) ÎQ "xÎX; "qÎQ,
y: X ´ Q ® Y	- функция выходов, т.е. y(x, q) Î Y "xÎX; "qÎQ.

Существуют следующие способы задания автоматов:

- с помощью таблицы. Функции j и y задаются таблицей, строки которой соответствуют буквам входного алфавита, а столбцы – состояниям. В пересечении строки a_j и столбца q_i помещается состояние
y (a_j, q_i), в которое переходит автомат из состояния q_i под воздействием входного символа a_j, и значение j (a_j, q_i), которое при этом появляется на выходе;

- в виде диаграммы. Состояния q_i изображаются на плоскости кружками, из которого проводится стрелка в q_u, если автомат, находящийся в состоянии q_i, при подаче некоторого входного символа может быть переведен в состояние q_u;

- совокупностью четверок вида: q_ia_j ® q_la_p,. Если на вход автомата, находящегося в состоянии q_i, в момент времени t подается символ a_j, то на выходе автомата в этот же момент времени появляется символ a_p, и в следующий момент времени t+1 автомат будет находиться в состоянии q_l.

- в виде системы булевых функций. Каждому q_j ÎQ взаимно-однозначно ставится в соответствие двоичная последовательность длины r - двоичный код a(q) = z₁z₂…z_r. Аналогично каждому a_iÎX и каждому b_k ÎY ставим взаимно-однозначно в соответствие двоичные последовательности b(a) = x₁x₂…x_k; g(b) = y₁y₂…y_s.В результате автомат будет задан системой булевых функций {j₁,j₂,…,j_r,y₁,y₂,…,y_s};

- в виде канонических уравнений. Если в момент времени t=1,2,… на вход автомата A=(X; Q; Y; j; y) последовательно подаются входные символы x(t)ÎX и при этом автомат находится в состоянии q(t)ÎQ, то под воздействием символа x(t) автомат перейдет в новое состояние q(t+1)ÎQ и выдаст выходной сигнал y(t). Величины x(t), y(t), q(t), q(t+1) связаны между собой следующими каноническими уравнениями:

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

Задачи анализа автоматов

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

Примеры выполнения заданий

1. Работа автомата задана таблично и выдает на выходе символ “*”, всякий раз, когда во входном алфавите встречается цепочка из комбинаций символов 0, 1, 2. Опишите работу автомата с помощью совокупности четверок. X = {0, 1, 2}, Y = {0, 1, 2} и Q = {q₀, q₁, q₂, q₃}. Определите, что распознает автомат.

Символы алфавита	С о с т о я н и я
q0	q1	q2	q3
	q1,1	q2,1	q0,0	q0,0
	q0,1	q0,1	q0,1	q0,1
	q0,2	q0,2	q3,1	q0,*

Решение:

q00® q11 q01® q01 q02® q02

q10® q21 q11® q01 q12® q02

q20® q00 q21® q01 q22® q31

q30® q00 q31® q01 q32® q0*

Автомат распознает цепочку вида: 1111*

2. Описание автомата - двоичного сумматора последовательного действия, задано с помощью совокупности четверок. X= {00, 01, 10, 11},
Y = {0, 1}, Q = {q₀, q₁}. Опишите работу автомата с помощью диаграммы.

q0<0,0> → q00 q0<0,1> → q01 q0<1,0> → q01 q0<1,1> → q10

q1<0,0> → q01 q1<0,1> → q10 q1<1,0> → q10 q1<1,1> → q11

Решение.

q1   (00,0)Ú(01,1)Ú(10,1) (01,0)Ú(10,0)Ú(11,1) (11,0) q1   q0     (00,1)

Задания для самостоятельного выполнения

4.1.1. Работа автомата задана с помощью совокупности четверок и выдает на выходе символ “ * ”, всякий раз, когда во входной последовательности алфавита {a, b} встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата таблично.

0)

q0b → q0b q0a → q1a

q1b → q2b q1a → q0b

q2b → q3b q2a → q0b

q3b → q0b q3a → *

1)

q0b → q1b q0a → q0b

q1b → q0b q1a → q2a

q2b → q3b q2a → q0b

q3b → q0b q3a → *

2)

q0a → q1a q0b → q0a

q1a → q2a q1b → q0a

q2a → q0a q2b → q3b

q3a → q0a q3b → *

3)

q0b → q1b q0a → q0b

q1b → q2b q1a → q0b

q2b → q0b q2a → q3a

q3b → q0b q3a → *

4)

q0a → q1a q0b → q0a

q1a → q2a q1b → q0a

q2a → q3a q2b → q0a

q3a → q0a q3b → *

5)

q0b → q1b q0a → q0b

q1b → q2b q1a → q0b

q2b → q3b q2a → q0b

q3b → q0b q3a → *

6)

q0a → q0a q0b → q1b

q1a → q0a q1b → q2b

q2a → q0a q2b → q3b

q3a → q0a q3b → *

7)

q0b → q0b q0a → q1a

q1b → q0b q1a → q2b

q2b → q0b q2a → q3b

q3b → q0b q3a → *

8)

q0a → q1a q0b → q0b

q1a → q0a q1b → q2b

q2a → q3a q2b → q0b

q3a → q0a q3b → *

9)

q0a → q0a q0b → q1b

q1a → q2a q1b → q0a

q2a → q3b q2b → q0a

q3a → q0a q3b → *

Решение:

Символы алфавита	С о с т о я н и я
q0	q1	q2	q3
a
b

4.1.2. Работа автомата задана таблично и выдает на выходе символ “&”, всякий раз, когда во входном алфавите встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата с помощью совокупности четверок.

0)

Символы входного алфавита	Состояния
q0	q1	q2	q3
О	q0,О	q2,О	q0,О	q0,О
К	q1,К	q0,О	q0,О	q0,О
Т	q0,О	q0,О	q3,Т	q0 &

1)

Символы входного алфавита	Состояния
q0	q1	q2	q3
С	q0,С	q2,С	q0,С	q0,С
О	q1,О	q0,С	q0,С	q0,С
А	q0,С	q0,С	q3,А	q0 &

2)

Символы входного алфавита	Состояния
q0	q1	q2	q3
М	q0,М	q0,М	q3,М	q0 &
А	q0,М	q2,А	q0,М	q0,М
С	q1,С	q0,М	q0,М	q0,М

3)

Символы входного алфавита	Состояния
q0	q1	q2	q3
А	q0,А	q2,А	q0,А	q0,А
Д	q1,Д	q0,А	q0,А	q0,А
Р	q0,А	q0,А	q3,Р	q0 &

4)

Символы входного алфавита	Состояния
q0	q1	q2	q3
О	q0,О	q2,О	q2,О	q0,О
Р	q1,Р	q0,О	q2,О	q0,О
М	q0,О	q0,О	q3,М	q0 &

5)

Символы входного алфавита	Состояния
q0	q1	q2	q3
Р	q0,Р	q0,О	q3,Р	q0 &
М	q1,М	q0,О	q0,О	q0,О
И	q0,Р	q2,И	q0,О	q0,О

6)

Символы входного алфавита	Состояния
q0	q1	q2	q3
А	q0,А	q2,А	q0,А	q0А
П	q1,П	q0,А	q0,А	q0,А
Р	q0,А	q0,А	q3,Р	q0 &

7)

Символы входного алфавита	Состояния
q0	q1	q2	q3
М	q0,М	q0,М	q3,М	q0 &
И	q0,М	q2,И	q0,М	q0,М
Р	q1,Р	q0,М	q0,М	q0,М

8)

Символы входного алфавита	Состояния
q0	q1	q2	q3
Р	q0,Р	q0,Р	q3,Р	q0 &
У	q0,Р	q2,У	q0,Р	q0,Р
Т	q1,Т	q0,Р	q0,Р	q0,Р

9)

Символы входного алфавита	Состояния
q0	q1	q2	q3
Л	q0,Л	q2,Л	q0,Л	q0,Л
Т	q1,Т	q0,Л	q0,Л	q0,Л
Я	q0,Л	q0,Л	q3,Я	q0 &

 

Решение:

q0 →	q1 →	q2 →	q3 →
q0 →	q1 →	q2 →	q3 →
q0 →	q1 →	q2 →	q3 →

 

4.1.3. Работа автомата задана с помощью диаграммы и выдает на выходе символ “*", всякий раз, когда во входном алфавите встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата с помощью совокупности четверок.

0) (б, б) (К, б) Ú (б, *) q0   q1       (К, К)	1) (м, м) (с, м) Ú (м, *) q0   q1       (с, с)
2) (б, б) (М, б) Ú (б, *) q0   q1       (М, М)	3) (г, г) (к, г) Ú (г, *) q0   q1       (к, к)
4) (б, б) (Г, б) Ú (б, *) q0   q1       (Г, Г)	5) (м, м) (д, м) Ú (м, *) q0   q1       (д, д)
6) (г, г) (м, г) Ú (г, *) q0   q1       (м, м)	7) (б, б) (Т, б) Ú (б, *) q0   q1       (Т, Т)
8) (а, а) (г, а) Ú (а, *) q0   q1       (г, г)	9) (м, м) (к, м) Ú (м, *) q0   q1       (к, к)

Решение:

q0 →	q1 →
q0 →	q1 →

4.2. Задачи синтеза автоматов

Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием.

Примеры выполнения заданий

1. Постройте конечный автомат, воспринимающий на входе двоичную последовательность и выдающий на выходе специальный символ
‘ *’, если во входной последовательности подряд встретится 4 единицы. В остальных случаях автомат на выходе повторяет входной символ.

Решение.

q00® q00 q01® q11

q10® q00 q11® q21

q20® q00 q21® q31

q30® q00 q31® q0*

 

2. Постройте конечный автомат таблично, представляющий двоичный сумматор последовательного действия.

Решение. Обозначим через q₀ и q₁ его состояния, соответствующие отсутствию и наличию переноса.

 

Символы алфавита	Состояния
x1	x2	q0	q1
		q0,0	q0,1
		q0,1	q1,0
		q0,1	q1,0
		q1,0	q1,1

Задания для самостоятельного выполнения

4.2.1. Постройте конечный автомат, выдающий на выходе символ “!”, всякий раз, когда во входной двоичной последовательности встречается:

0) последовательность 0000;

1) последовательность 1111;

2) последовательность 0110;

3) последовательность 0111;

4) последовательность 1000;

5) последовательность 0011;

6) последовательность 0010;

7) последовательность 1110;

8) последовательность 0001;

9) последовательность 1100.

4.2.2. Постройте конечный автомат, выдающий на выходе символ “♫”, всякий раз, когда во входной последовательности в алфавите

0) {А, н, ю, т} встречается имя “Анюта”;

1) {А, л, е, ш} встречается имя “Алеша”;

2) {И, р, н, а} встречается имя “Ирина”;

3) {С, а, ш} встречается имя “Саша”;

4) {Д, а, я, н} встречается имя “Даяна”;

5) {Н, и, а} встречается имя “Нина”;

6) {А, н, ж, е, л} встречается имя “Анжела”;

7) {А, н, т, о} встречается имя “Антон”;

8) {С, е, р, ж, а} встречается имя “Сережа”;

9) {Л, и, я} встречается имя “Лилия”.