Національний технічний університет України

Національний технічний університет України

« Київський політехнічний інститут »

Факультет інформатики та обчислювальної техніки

Кафедра автоматики та управління в технічних системах

Контрольна робота № 1

з курсу «Основи дискретної математики»

Варіант №2

Виконав

Студент групи ІA-23

Щербаков Д.О.

Перевірив:

Дорогий Я.Ю.

Київ 2012

Вправа 1

Розглянемо скінчений автомат, розглянутий у вправі З теми 5.1. Вхідний алфавіт визначено на основі вхідного алфавіту скінченого автомату Е = { 0,1, 2, e}. Множину станів запишемо без змін A = {a0, a1, a2}. Нехай алфавіт магазину D містить множину символів {d0, 0, 1, e}, початковий та заключний стани залишимо без змін. Нехай d0 - початковий символ магазину. Тоді МП-автомат

<{ 0,1, 2, e}, {a₀, a₁, a₂}, {d₀, 0, 1, e}, f₃, a₀, d₀, a₂>

буде допускати такі ж самі слова, що й скінчений автомат із вправи 3 теми 5.1, якщо значення f₃ будуть збігатися із значеннями функції переходів скінченого автомату. Іншими словами, наступний стан буде залежати тільки від попереднього стану та вхідного символу, а у магазин буде занесений вхідний символ:

f₃ (a0,0,d0) = (a0,0); f₃ (a0,0,0) = (a0,00);

f₃ (a0,2,d0) = (a2,2); f₃ (a0,2,0) = (a2,20);

f₃ (a0,1,d0) = (a1,1); f₃ (a0,1,0) = (a1,10);

f₃ (a1,1,1) = (a1,11); f₃ (a0,2,1) = (a2,21);

f₃ (a1,0,1) = (a0,11).

Автомат з магазинною пам’яттю допускає такі ж самі слова, що і скінчений автомат із п. І вправи 3 теми 5.1, без спустошення магазину, причому при досягненні заключної конфігурації, що характеризується заключним станом a₂ та пустим символом на вході, магазин буде містити вихідне слово скінченного автомата для вхідної послідовності, що аналізується.

Розглянемо, наприклад, роботу автомата з магазинною пам’яттю над вхідною послідовністю 001012:

(a₀,0010112,d0)| (a₀,010112,0)| (a₀,10112,00)|

(a₁,0112,100)| (a₀,112,0100)| (a₀,12,10100)|

(a₁,2,110100)| (a₀ ,e,2110100).

Оскільки досягнуто заключної конфігурації, то слово 0010112 є допустимим.

Вправа 4

Детермінований автомат завершує роботу лише тоді, коли досягає кінцевого стану.

á{0,1}, {a₀, a₁, a₂}, {d₀, 0}, f₃, a₀, d₀, {a₀} ñ, де відображення f₃ визначено в такий спосіб:

f₃(a₀, 0, d₀) = {(a₁, 0d₀)}

f₃(a₁, 0, 0) = {(a₁, 00)}

f₃(a₁, 1, 0) = {(a₂, e)}

f₃(a₂, 1, 0) = {(a₂, e)}

f₃(a₂, e, d₀) = {(a₀, e)}

приклад деяких дій

(a₀, 01, d₀) |® (a₁, 1, 0d₀)

(a₁, 1, 0d₀) |® (a₂, e, d₀)

(a₂, e, d₀) |® (a₀, e, e) - заключна конфігурація, тобто вхідна програма 01 допускається.

Вправа 7

якщо відображення f₃ становить собою функцію, МП-автомат назвемо детермінованим

автомат á{1,2}, {b₀, b₁, b₂}, {d₀, 0}, f₃, b₀, d₀, {b₀} ñ, де відображення f₃ визначено в такий спосіб:

f₃(a₀, 1, d₀) = {(b₁, 1d₀)}

f₃(a₁, 1, 1) = {(b₁, 11)}

f₃(b₁, 2, 1) = {(b₂, e)}

f₃(b₂, 2, 1) = {(b₂, e)}

f₃(b₂, e, d₀) = {(b₀, e)}

Вправа 10

Чому неможливо побудувати автомат з магазинною пам’яттю, який допускає мову АБВ, ААББВВ, АААЕБЕВВВ,...? 3’ясувати труднощі, які зустрілися б у випадку намагання побудувати цей автомат з магазинною пам’яттю.

Рішення:
Тому що, ми не можемо задати відповідну граматику для мови АБВ, ААББВВ, АААЕБЕВВВ,...

При спробі завдання такої граматика таблиця переходів була б нескінченної довжини.

Вправа 13

Поставити діагностичний безумовний експеримент для пар станів:

1) а₁ і а₂; 2) а₁₁ і а₁₂; 3) а₃ і а₁₀; 4) а₁₂ і а₁₃;

5) а₁ і а₁₃; 6) а₄ і а₅; 7) а₁ і а₉; 8) а₂ і а₁₃;

9) а₁₁ і а₁₂; 10) а₈ і а₁₃; 11) а₅ і а₇; 12) а₁₁ і а₁₃.

скінченого автомату, заданого такою таблицею переходів:

	ai+1	bi
a1	a1	A2
a2	a1	A2
a3	a4	A5
a4	a6	A7
a5	a11	a12
a6	a9	a10
a7	a7	A1
a8	a1	A1
a9	a13	A9
a10	a5	A4
a11	a9	a11
a12	a8	A3
a13	a9	a13
a14	a9	a14

1) f₁(а₁,0)= а_1,f₁(а₂,0)= а₁, f₁(а₁,1)= а_2,f₁(а₂,1)= а₂,

f₂(а_1,0)=0, f₂(а_2,0)=0, f₂(а_1,1)=1, f₂(а_2,1)=1;

2) f₁(а₁₁,0)= а_9,f₁(а₁₂,0)= а₈, f₁(а₁₁,1)= а_11,f₁(а₁₂,1)= а₃,

f₂(а_11,0)=0, f₂(а_12,0)=0, f₂(а_11,1)=1, f₂(а_12,1)=1;

3) f₁(а₃,0)= а_4,f₁(а₁₀,0)= а₅, f₁(а₃,1)= а_5,f₁(а₁₀,1)= а₄,

f₂(а_3,0)=1, f₂(а_10,0)=1, f₂(а_3,1)=1, f₂(а_10,1)=1;

4) f₁(а₁₂,0)= а_8,f₁(а₁₃,0)= а₉, f₁(а₁₂,1)= а_3,f₁(а₁₃,1)= а₁₃,

f₂(а_12,0)=0, f₂(а_13,0)=0, f₂(а_12,1)=1, f₂(а_13,1)=1;

5) f₁(а₁,0)= а_1,f₁(а₁₃,0)= а₉, f₁(а₁,1)= а_2,f₁(а₁₃,1)= а₁₃,

f₂(а_1,0)=0, f₂(а_13,0)=0, f₂(а_1,1)=1, f₂(а_13,1)=1;

6) f₁(а₄,0)= а_11,f₁(а₅,0)= а₉, f₁(а₄,1)= а_12,f₁(а₅,1)= а₁₀,

f₂(а_4,0)=1, f₂(а_5,0)=1, f₂(а_4,1)=0, f₂(а_5,1)=0;

7) f₁(а₁,0)= а_1,f₁(а₉,0)= а₁₃, f₁(а₁,1)= а_2,f₁(а₉,1)= а₉,

f₂(а_1,0)=0, f₂(а_9,0)=0, f₂(а_1,1)=1, f₂(а_9,1)=1;

8) f₁(а₂,0)= а_1,f₁(а₁₃,0)= а₉, f₁(а₂,1)= а_2,f₁(а₁₃,1)= а₁₄,

f₂(а_2,0)=0, f₂(а_13,0)=0, f₂(а_2,1)=1, f₂(а_13,1)=1;

9) f₁(а₁₁,0)= а_9,f₁(а₁₂,0)= а₈, f₁(а₁₁,1)= а_11,f₁(а₁₂,1)= а₃,

f₂(а_11,0)=0, f₂(а_12,0)=0, f₂(а_11,1)=1, f₂(а_12,1)=1;

10) f₁(а₈,0)= а_1,f₁(а₁₃,0)= а₉, f₁(а₈,1)= а_1,f₁(а₁₃,1)= а₁₃,

f₂(а_8,0)=0, f₂(а_13,0)=0, f₂(а_8,1)=1, f₂(а_13,1)=1;

11) f₁(а₅,0)= а_11,f₁(а₇,0)= а₇, f₁(а₅,1)= а_12,f₁(а₇,1)= а₁,

f₂(а_5,0)=1, f₂(а_7,0)=1, f₂(а_5,1)=0, f₂(а_7,1)=0;

12) f₁(а₁₁,0)= а_9,f₁(а₁₃,0)= а₉, f₁(а₁₁,1)= а_11,f₁(а₁₃,1)= а₁₃,

f₂(а_11,0)=0, f₂(а_13,0)=0, f₂(а_11,1)=1, f₂(а_13,1)=1.

Вправа 16

Задати таблицю дій машини Тюрінга, що допускає тільки ланцюжки мови з вправи 36 теми 4.1.

Розв'язання:

Стан	Клітинка, яка розглядається 0	Клітинка, яка розглядається I
		L1
	L2	L5
	PR4	L2
	R6	R3
	R2	R4
	L3	L7
	L4	EL7
	C0	EL11
	PC0	L11

Дата добавления: 2015-09-29