Тема 5. Елементарна теорія автоматів

У результаті вивчення теми студенти повинні вміти:

- будувати елементарні скінчені автомати;

- будувати елементарні автомати з магазинною пам’яттю;

- будувати та аналізувати алгоритм для машини Тьюринга.

Контрольні питання:

1. Машина Тьюрінга.

2. Тезис Черча-Тьюринга.

3. Розпізнавання рядків.

4. Мови, що розпізнаються.

5. Лінійно-обмежені автомати.

Контрольні завдання:

1. Нехай машина Тьюринга задана таблицею. Визначте, який вид буде мати інформація на стрічці після зупинки машини, якщо на початку роботи на вхід подано рядок (голівка встановлена на підкреслений символ) «...λλ 0 10110λλ...»?

2. Побудувати машину Тьюринга (алфавіт стрічки {0,1}), яка розпізнає рядки виду 0ⁿ1ⁿ;

3. Побудувати машину Тьюринга (алфавіт стрічки {0,1}), яка змінює перший 0 на стрічці на 1 і решту символів залишає без зміни;

4. Побудувати машину Тьюринга (алфавіт стрічки {0,1}), яка змінює всі символи 1 на стрічці на 0, крім лівої одиниці;

5. Побудувати машину Тьюринга (алфавіт стрічки {0,1}), яка розпізнає рядки, що закінчуються нулем.