Тема 5.2. Нескінчені автомати

[1, гл.2. розд.5; 4, гл. 16. § 6Б; 2, гл.З, § 7; 4. гл.Іб., §6В ]

Вказівки щодо використання літературних джерел.

Слід спробувати задати скінченим автоматом контекстно-вільну мову, яка не є регулярною. Переконавшися у неможливості цього, перейти до ускладнення уявлень про стрічкові автомати за рахунок додавання допоміжної пам’яті типу магазин, потенційно нескінченої.

Уточнити особливості детермінованих автоматів з магазинною пам’яттю, різноманітні варіанти зупинок автоматів. Після цього порівняти автомати з магазинною пам’яттю й контекстно-вільні граматики як два способи задання контекстно-вільних мов, ознайомитися з проблемами трансляції й роллю автоматів з магазинною пам’яттю як перетворювачів (трансляторів).

Для машини Тьюрінга, як і для іншого автомата, для задання її роботи важливо знати загальні правила. функціонування.

Машина Тьюрінга - перший з автоматів, на основі якого сформувалося уявлення про інші автомати, Вона широко використовується у математичній логіці, основах математики.

Необхідно порівняти машину Тьюріїнга і граматики без обмежень, лінійно обмежений автомат і контекстно -залежні граматики як різні способи задання мов типу відповідно 0 і 1; сформувати уявлення про обчислювальну функцію як функцію для якої можна побудувати машину Тьюрінга.

Вправи до теми 5.2.

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

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

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

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

f₃ (a₀ ,0,d₀ ) = (a₀ ,0); f₃ (a₀ ,0,0) = (a₀ ,00);

f₃ (a₀ ,2,d₀ ) = (a₂ ,2); f₃ (a₀ ,2,0) = (a₂ ,20);

f₃ (a₀ ,1,d₀ ) = (a₁ ,1); f₃ (a₀ ,1,0) = (a₁ ,10);

f₃ (a₁ ,1,1 ) = (a₁ ,11); f₃ (a₀ ,2,1) = (a₂ ,21);

f₃ (a₁ ,0,1 ) = (a₀ ,11).

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

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

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

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

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

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

Вправа 2. Задати автомат з магазинною пам’яттю, який допускає мову, яку породжують граматики з вправи 16 теми 4.1.

Вправа 3. Описати два способи завершення автоматом з магазинною пам’яттю роботи над словом.

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

Вправа 5. Для МП-автомату з вправи 4 навести автомат з магазинною пам’яттю, що допускає ту ж мову спустошенням магазину.

Вправа 6. Вказати особливості недетермінованих автоматів з магазинною пам’яттю, що впливають на означення допустимих слів.

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

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

Вправа 9. Навести приклади автомату з магазинною пам’яттю та розширеного автомату з магазинною пам’яттю, що допускають однакову мову.

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

Вправа 11. Задати автомат, що допускає мову:

І) L = {А,ААБ, АААББ, ААААБББ,...}

2) L = {АББ, ААБББ, АААББББ,...}

З) L = {АБ, ААБВ, АААБВВ,...}

4) L = {АБВ, ААБВВ, АААБВВВ,...}

5) L = {АБВВ, ААБВВВ, АААБВВВВ,...}

6) L = {АБВ, АБВВ, АБВВВ,...}

7) L = {АБВВ, ААБВВ, АААБВВ,...}

8) L = {АБВВ, АББВВ, АБББВВ,...}

9) L = {ВВ,АВВ,АААВВ,...}

Приклад: Нехай маємо мову L = {ВВ, ABB, ААВВ, АААВВВ, ...}. Вхідний алфавіт E = {A, B, e}. Нехай початковий стан – a₀ . Стан a₁ будемо використовувати, щоб зафіксувати появу символів А, а стан a₂ - символів B. Нехай a₃ буде заключний стан, який разом із символом е на вхідному рядку буде характеризувати заключну конфігурацію. Нехай d₀ - початковий символ магазину. У магазин будемо також записувати символи А і е. Таким чином, D = {e, d₀, A}, А = {a₀, a₁, a₂, a₃}.

Залишається визначити відображення f₃ . Використовуючи зауваження про стани, задамо f₃ так:

f₃(a₀, A,d₀ )= (a₁, Ad₀); f₃(a₀, B,d₀ )= (a₂, d₀);

f₃(a₁, A, A )= (a₀, e); f₃(a₁, B,A )= (a₂, e);

f₃(a₂, B, d₀ )= (a₃, e).