Тема 5.2

Вправа 1. Задати автомат з магазинною пам’яттю, що допускає таку ж мову, а також скінчений автомат, заданий у вправі 3 теми 5.1.

Вправа 4 Навести приклад автомату з магазинною пам’яттю, який завершує роботу над словом, потрапляючи у один із заключних станів після перегляду останнього символу слова

Вправа 7 Навести приклад детермінованого автомату з магазинною пам’яттю.

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

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

Відповідь:

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

<{ 0,1, 2, e}, {a0, a1, a2}, {d0 , 0, 1, e}, f3, a0 , d0 , a2>

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

f3 (a0 ,0,d0 ) = (a0 ,0); f3 (a0 ,0,0) = (a0 ,00);

f3 (a0 ,2,d0 ) = (a2 ,2); f3 (a0 ,2,0) = (a2 ,20);

f3 (a0 ,1,d0 ) = (a1 ,1); f3 (a0 ,1,0) = (a1 ,10);

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

f3 (a1 ,0,1 ) = (a0 ,11).

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

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

(a0,0010112,d0)| (a0 ,010112,0)| (a0 ,10112,00)|

(a1,0112,100)| (a0 ,112,0100)| (a0 ,12,10100)|

(a1,2,110100)| (a0 ,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₂, , d₀)

(a₂, , d₀)  (a₀, , ) - заключна конфігурація, тобто вхідна програма 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. Тому що, ми не можемо задати відповідну грамматику для мови АБВ, ААББВВ, АААЕБЕВВВ, ...

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

16.

Стан	Клітинка, яка розглядається 0	Клітинка, яка розглядається I
1	20	L1
2	L2	L5
3	PR4	L2
4	R6	R3
5	R2	R4
6	L3	L7
7	L4	EL7
8	C0	EL11
9	PC0	L11