1. Нехай цілі числа задано як ланцюжки символів «1». Побудувати нормальний алгоритм Маркова, що реалізує додаваннячисел.
Розв’язання.
Алфавіт алгоритмічної системи А = {1,+}. Правила підстановок.
Р = {1 + 1 ® 11+, 1+ ® 1}
Граф-схема алгоритму додавання (рис. 3.6):
Рис. 3.6. Граф-схема алгоритму додавання
|
Перевірка: 5 + 2 = 7;
Вхідний ланцюжок: 11111 + 11
11111+11
111111+1
1111111+
Вихідний ланцюжок: 1111111.
2. За умовами задачі 1 побудувати нормальний алгоритм Марко-ва віднімання чисел.
3. Побудувати нормальний алгоритм Маркова переведення чисел з десяткової системи у двійково-десяткову (кожна десяткова цифра замінюється її двійковим кодом).
4. Побудувати нормальний алгоритм Маркова представлення двійкових чисел у прямому коді, якщо воно невід’ємне, або в оберненому коді, якщо воно від’ємне.
5. Задано машину Тьюринга зовнішнім алфавітом А = {0, 1, *} та внутрішнім алфавітом Q = {q0, q1, q2, q3}, де q0 — порожній символ, q3 — заключний стан. Програму машини Тьюринга задано у вигляді таблиці відповідності:
 А
Q
|
|
| *
|
|
| q2OЛ
| q0 Л
| q3 O
|
| q1
| q1 П
| q0 Л
| Q + П
|
| q2
| q2 Л
| q1 1
| q2 Л
|
| q3
| останов
|
|
Побудувати алгоритми додавання двох чисел та записати відповідні конфігурації машини, якщо задано початкові конфігурації
1) q0111*11
2) q011111*111
3) q00011*0011.
6. Абстрактний автомат Мілі (I роду) задано трьома множинами: вхідним алфавітом А = {x, y}, вихідним алфавітом B = {u, v}, множиною станів S = {1, 2, 3, 4} та двома функціями (переходів та виходів) у вигляді таблиць:
Таблиця переходів Таблиця виходів
|
|
|
|
|
|
|
|
|
|
|
|
| x
|
|
| –
|
|
| x
| v
| u
| –
| u
|
| y
|
|
|
|
|
| y
| u
| v
| u
| u
|
Вхідні слова: xxyyxx, xyxyxxy,
yyyxxx, yxxxy.
Побудувати алгоритми визначення вихідних слів.
7. Задано схему Р граматики G
P = {D à ABB, C à DCD, C à AB, Bà A}.
Визначити VT, VH, S і мову L(G).
Побудувати виводи граматики та визначити їх довжину.
8. Задано граматику G словником V = {A, B, C, D, E} та схемою правил P:
P = {E à DCD, E à A, D à BC, D à C, A à BB}.
Визначити VT, VH, S граматики G, побудувати мову L(G), виводи граматики та визначити їх довжину.
9. Нехай маємо породжувальну граматику G = {VT, VH, P, S}, де VH = {S, A, B, C, D} — нетермінальний словник, символи якого означають :
S — дієслово (виділений символ);
A — корінь;
B — префікс;
C — суфікс;
D — закінчення;
VT = {b, c, d, e, f, i, j, k, l}, символи якого означають:
е — біг, d — ляк, i — пере,
b — кид, j — ви, k — ти,
с — трим, f — за, l — а.
Правила підстановок:
P = {S à ACD; B à і; B à j; B à f; A à b; A à c; A à d;
A à e; C à l; D à k}.
Побудувати схему граматики, визначити за нею всі термінальні ланцюжки та виділити з них ті, що належать до природньої мови.
Завдання для перевірки знань
1. Визначення алгоритмічної системи.
2. Поняття припустимої операції.
3. Типи алгоритмічних систем.
4. Поняття рекурсивної функції.
5. Визначення нормальних алгоритмів Маркова.
6. Визначення машини Поста.
7. Визначення машини Тьюринга.
8. Визначення абстрактного автомата.
9. Типи абстрактних автоматів та їх використання.
10. Визначення формальних граматик.
11. Типи, особливості формальних граматик та їх використання.
12. Алгоритмічна структура ЕОМ.
13. Чому рекурсивні функції можна використовувати у теорії алгоритмів?
14. Типи припустимих операцій в алгоритмічних системах.
15. Які операції можна виконувати над рекурсивними функціями?
16. Сутність операції суперпозиції.
17. Сутність операції примітивної рекурсії.
18. Сутність операції найменшого кореня.
19. Технологія обробки інформації за нормальним алгоритмом Маркова.
20. Два типи нормальних алгоритмів.
21. Композиція нормальних алгоритмів Маркова.
22. Складові частини машини Поста.
23. Представлення алгоритмів у машині Поста.
24. Складові частини машини Тьюринга.
25. Порівняння машин Поста і Тьюринга.
26. Модифікація машини Тьюринга.
27. Представлення алгоритмів у машині Тьюринга.
28. Технологія функціонування абстрактного автомата.
29. Автомати I та II роду.
30. Принцип дії абстрактних автоматів.
31. Способи завдання абстрактних автоматів.
32. Табличний спосіб завдання абстрактних автоматів.
33. Графічний спосіб завдання абстрактних автоматів.
34. Функціональний спосіб завдання абстрактних автоматів.
35. Контекстовільні граматики та їх застосування.
36. Контекстозалежні граматики та їх застосування.
37. Основні класи задач математичної лінгвістики.
ТЕМА 4.КЛАСИФІКАЦІЯ ЗАДАЧ
І ПРОЦЕСІВ ОБРОБКИ ІНФОРМАЦІЇ
