Розділ 2.
Еталонні моделі літерної обробки
20000032В даному розділі розглядається еталонна модель одного з найпростіших,
але водночас найфундаментальніших різновидів обробки слів. Поняття слова
уточнюється як об’єкт, зіставлений з літер, що відповідає праволінійному типу
граматики за ієрархією Хомського. Елементарними засобами обробки слів є
операції приписування літери до кінця слова. Задачею розділу є породження такої
системи композицій, яка б адекватно описувала процеси програмування обробки
слів при зазначених вихідних положеннях.
2.1. Літерна структура слів та базові функції над словами
Слова в даній моделі розглядаються виключно крізь призму властивості бути
зіставленими з літер. Тоді експлікація поняття слова зводиться до експлікації
поняття зіставлення. Його розгортання вимагає виявити базові дії над словами,
здійсненність яких з необхідністю слідує з обраного типу абстракції у розгляді
слів. Основою для побудови слів шляхом приписування літер є порожнє слово. Дане
поняття адекватно уточнюється індивідуалізацією в універсумі слів спеціального
об’єкту , для якого постулюється можливість відрізнити його від будь-якого
іншого об’єкту та можливість породжувати його. Останнє, в свою чергу,
уточнюється введенням базової операції-константи.
Для відображення поняття літери суттєво, що з літер можливо зіставити будь-яке
слово, тобто клас слів є в точності множиною тих об’єктів, які можливо породити
за допомогою операцій зіставлення. Суттєво також те, що літерна зіставленість
вичерпно характеризує слово: два слова є однаковими тоді і тільки тоді, коли
вони однаково зіставлені з літер. Відповідно до принципів ЕП, літера як
сутність проявляє себе лише через відношення з іншими об’єктами, а саме зі
словами. Це означає, що експліцитна модель має описувати не літери як такі, а
літери крізь призму операцій зіставлення.
Зазначені основні засади адекватно уточнюються наступним означенням. Нехай
задана деяка скінченна і непорожня множина з об’єктів, що (в загальному
випадку) не є об’єктами даних, . Множину домовимося називати алфавітом, а
об’єкти — літерами.
Означення 21.1. Функціями правого приписування літер назвемо -індексоване
сімейство тотальних функцій типу , , причому 1) множина є замикання множини
відносно множини операцій ; 2) для будь-яких літер та для будь-яких слів
рівність має місце тоді і тільки тоді, коли та . Слова в такому випадку
називаємо словами в алфавіті .
Іншими словами, алгебра слів відносно операцій є вільною, не містить
нетривіальних тотожностей. Виходячи із змістовного уявлення про предмет, що
моделюється, є підстави запровадити для застосування функції приписування нове
позначення: .
Означення 22.2. Функціями правого відсічення літери будемо називати
-індексоване сімейство часткових функцій типу , , таких, що
Згідно п. 2 означення 2.1 таке , якщо існує, то єдине, тому результат
відсічення визначається однозначно, і означення коректне.
Природно вважати операції композиціями над словами, а операції дуальними до
них декомпозиціями. Функції приписування (але не відсічення) зафіксуємо як
базові функції над словами.
Означення 23.3. Четвірка є система літерних слів.
2.2. Композиційна система літерної обробки
Поняття ІМ має широке коло можливих конкретизацій, що дає можливість адекватно
моделювати найрізноманітніші програмні поняття та структури. Тому слід виявити
характерний для СО тип іменних даних. Аналіз предмету дозволяє зробити
висновок, що денотати імен в СО не можуть в свою чергу мати структуру іменних
множин, на противагу програмуванням зі складними структурами даних, а також не
можуть самі виступати іменами, на противагу системам з непрямим іменуванням
(або метаіменуванням). Важливе у багатьох практичних застосуваннях та для
теоретичних досліджень явище геноіменування, яке полягає в тому, що імена
породжуються як значення деяких функцій, також не є характерною сутнісною рисою
СО.
Таким чином, є підстави для базового припущення, що імена в СО не є об’єктами
обробки, а в ролі денотатів можуть виступати лише слова. Отже, універсум даних
складається з класу слів та класу -іменних множин слів . Всюди далі в даній
роботі вважаємо, що клас достатньо широкий, що дає змогу використовувати в
композиційних термах довільну апріорі необмежену кількість імен.
Означення 24.4. Права іменна літерна диз’юнкція. Якщо функція іменна -арна типу
, , …, — іменні функції, відповідно , …, -арні, — ім’я, то
є -арна, , іменна функція, така, що
де , .
Серед загальнопрограмологічних композицій візьмемо мультиплікацію , заміщення ,
обмеження та видалення, а також сімейство рекурсій . Базовими функціями над
несимвольними даними є функції іменування та розіменування та тотожна функція
над іменними множинами . Базовими функціями над словами є -арна
функція-константа , така, що , та сімейство функцій правого приписування.
Означення 25.5. Композиційна система літерної обробки є трійка , де , , .
2.3. Найпростіші похідні функції літерної обробки
Задача даного та наступних підрозділів — показати, що синтез завідомо
правильних програм в даній композиційній системі є зручним та природним. Не
будемо доводити очевидну можливість виразити тотожну функцію над словами та
всюди невизначених функцій над словами та над ІМ, відповідно та .
Лема 26.1. В системі можливо виразити будь-яку функцію-константу , таку, що
для довільного слова .
Доведення. Для лема справедлива, оскільки функція з потрібною властивістю
належить до числа базових. Нехай в системі можливо виразити функцію для
деякого . Розглянемо слово . Тоді дане слово породжується функцією . Отже, за
індукцією, твердження має місце для б
- Київ+380960830922