Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, - не плоский.

Решение:

Не выполняется неравенство 3 V - 6 ≥ E.

Семиугольник разбит на выпуклые пяти- и шестиугольники, причем так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

Решение:

Докажите сначала неравенство E £ 3V - 6, используя то, что из каждой вершины выходит по крайней мере 3 ребра. Обозначим количество пятиугольников через a, количество шестиугольников через b.

Заметим, что 5a + 6b + 7 = 2E £ 6F – 12 = 6(a + b + 1) – 12. Отсюда a ³ 13.

4. Граф задан геометрически. А) Определите, содержит ли данный граф гамильтонов цикл? Б) Выпишите гамильтонов цикл у данного графа, если он есть:

Решение:

А) да, содержит, т.к. граф – полный и не содержит перекладин и висячих вершин.

Б) гамильтонов цикл выделен сплошной линией: (1,2), (2,3), (3,4), (4,5), (5,1).

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

 

Запишите: 1) любой путь, не являющийся цепью; 2) цепь и простую цепь; 3) цикл, простой цикл, если таковые имеются.

 

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

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

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

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

Практическое занятие №9. Автоматы

Система 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)

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

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

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 →

 

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 →