Національна академія наук України
Інститут кібернетики імені В.М. Глушкова

МЕЙТУС Володимир Юлійович

УДК 519.713+512.58+004.4

КАТЕГОРНІ МЕТОДИ В ТЕОРІЇ МОВНИХ

ПЕРЕТВОРЮВАЧІВ

01.05.03 – математичне та програмне забезпечення
обчислювальних машин і систем

Автореферат

дисертації на здобуття наукового ступеня

доктора фізико-математичних наук

Київ - 2008

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики ім. В.М. Глушкова НАН України.

Офіційні опоненти: доктор фізико-математичних наук, професор,

член-кореспондент НАН України

Летичевський Олександр Адольфович,

Інститут кібернетики ім. В.М. Глушкова

НАН України, завідувач відділу,

доктор фізико-математичних наук, професор

Дорошенко Анатолій Юхимович,.

Національний технічний університет

України «КПІ», професор,

доктор фізико-математичних наук, професор,

Глибовець Микола Миколайович,

Національний університет Києво-Могилянська

академія, завідувач кафедри інформатики.

Захист відбудеться 20 червня 2008 р. об 11 годині на засіданні

спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики

ім. В.М. Глушкова НАН України за адресою:

03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту.

Автореферат розісланий 06 травня 2008 р.

Учений секретар

спеціалізованої вченої ради В.Ф. СИНЯВСЬКИЙ

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Однозначність форми та принципів роботи комп’ютера вимагали строгої формалізації мов спілкування з ними. Це призвело до необхідності створення формальних схем завдання мовних перетворювачів, які б здійснювали відображення цих мов. Виникають різні складні проблеми. З одного боку, треба побудувати алгоритми та засоби, які їх реалізують, а з іншого – виникають проблеми доведення еквівалентності використаних схем цим алгоритмам. Заздалегідь невідомо, чи можна взагалі побудувати такі алгоритми. Це проблеми розв’язуваності та нерозв’язуваності, які виникають при дослідженні алгоритмів

Однак без вирішення цих задач неможливо обійтися. Тому розробка теорії мовних перетворювачів представляє інтерес як один з основних напрямків теоретичного обґрунтування і практичного вживання процесів з використанням мовних методів і засобів завдання інформації в сучасних комп'ютерних системах.
Фактично, будь-які дії направлені на створення програмного забезпечення та пов'язані з використанням комп'ютерів, так чи інакше представляються у вигляді перетворення мовних виразів.

Використання комп'ютерів для вирішення будь-яких завдань обов'язково пов’язано із задачами мовного подання і перетвореннями одних мовних виразів в інші. Цим визначаються численні дослідження, які використовують різні форми подання формальних мов і відображення одних мов в інші. А сам напрямок цих досліджень буде залишатися актуальним до того часу, доки людство буде використовувати комп’ютери, існуючі у сучасних вигляді та формі, які використовують сучасну структуру та логіку роботи.

Над розробкою теорії і практики використання формальних мов, автоматів та перетворювачів плідно працювали видатні українські учені Глушков В.М., Летичевський О.А., Капітонова Ю.В., Ющенко К.Л., Редько В.Н., Анісімов А.В, Вельбицький І.В., Лісовик Л.П., результати яких склали велику частину сучасної ін-форматики. Значний внесок у розвиток цього напрямку зробили вчені Росії та інших країн світу: Ляпунов А.А., Єршов А.П., Гладкий А.В., Лавров С.С., Братчи-
ков І.Л., Діковський О.Я., Кнут Д., Гінзбург С, Хомський Н., Грейбах Ш.,
Хопкрофт Д., Ахо А., Кореньяк А., Ульман Д., Чулик Д., Леман Д., Дійкстра 3., Флойд Р., Ландвебер П., Льюіс Р., Стірнз Р., Гарісон М., Розенкранц Д., Шютценберже М.

У більшості робіт були отримані результати, які не тільки є фундаментом ін-
форматики, але й залишаються актуальними і зараз, оскільки створені методи і підходи, які розвиваються й модифікуються, дозволяють вирішувати нові задачі і проблеми, що постійно виникають в науці. Найчастіше це спостерігається при створенні методів, заснованих на використанні математичного апарату, що дозволяє по-новому подивитись на проблему. У цій дисертації як такий апарат використовуються методи теорії категорій, інформатики, що розвинуті стосовно кола проблем, які зв'язані з мовними перетворювачами. Використанню категорного апарату в його застосуванні до різних аспектів теорії формальних мов присвячені роботи Ляпунова А., Шрейдера Ю., Ейленберга М., Райта Д., Арбіба М., Бенсона Д., Гогена Д., Лоувера В., Ламбека Д., Мейнса Е., Тетчера Д., Вагнера З.

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

Зв'язок з науковими програмами, планами, темами. Робота, яка розглядається, виконувалася протягом декількох років в Інституті кібернетики

ім. В.М. Глушкова. Окремі результати були одержані при розробці тем, що виконувалися за завданням ГКНТ СРСР і Держплану СРСР: Проблема 0.80.21, тема 04.07 "Розробити і запровадити в експлуатацію систему автоматизованого проектування АСУ (номер державної реєстрації 81085935) і проблеми 0.80.02 "Створити і запровадити в практику проектних організацій систему автоматизованого проектування і тиражування АСУ ..."(номер державної реєстрації 80059902), а також при розробці Республіканської автоматизованої системи РАС УРСР.

Мета і задачі дослідження. Метою роботи є розробка загальної методології вирішення проблем комп'ютерної переробки інформації на основі теоретико-категорних представлень, алгебраїчних теорій та розробка методів розв'язання проблем, які виникають при перетворенні інформації, представленої за допомогою
формальних мов. До цих методів належать такі:

• розробка категорного подання мов, включаючи їх синтаксис і семантику;

• категорне подання автоматів, що дозволяє надалі використовувати розроблені форми при аналізі мовних проблем та пошуку засобів вирішення проблем теорії;

• розробка методів побудови й аналізу категоріальних систем;

• використання таких систем для аналізу проблем існування скінченних мовних перетворювачів, пов'язаних з регулярними мовами, і використання цих представлень в дослідженнях відкритих проблем, зокрема проблеми Гінзбурга–Хіббарда;

• розробка алгоритмів аналізу та синтезу різних класів М-систем, які використовують пам'ять для визначення форм перетворення одних мов в інші;

• категорне подання магазинних автоматів, розв’язання відкритої проблеми еквівалентності детермінованих магазинних автоматів та інших, пов'язаних з нею відкритих проблем;

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

Об'єкт дослідження - процеси переробки дискретної інформації, що представляються за допомогою формальних мов.

Предмет дослідження - формальні конструкції мовних перетворювачів і відносин між мовами, пов'язаними з такими перетворювачами.

Методи дослідження. Основним методом дослідження є використання алгебраїчного подання мовних конструкцій у вигляді тих або інших категорних схем з подальшим застосуванням отриманих математичних об'єктів стосовно низки відомих проблем теорії мов і суміжних областей інформатики, і, зокрема, стосовно проблем еквівалентності мовних перетворювачів. Розглядаються методи аналізу та синтезу перетворювачів, методи теорії рекурсивних функцій, теорії груп та напівгруп, методи теорії алгоритмів. Розроблені схеми застосовувалися і при аналізі проблем побудови систем переробки інформації при створенні автоматизованих систем управління.

Наукова новизна отриманих результатів. У роботі отримали подальший розвиток теоретико-категорні подання формальних мов, граматик і мовних перетворювачів з метою розробки нових методів вирішення проблем інформатики.

Уперше

• розроблено категорне подання синтаксису та семантики формальних мов, категорних автоматів;

• запропонований новий підхід до дослідження автоматів і перетворювачів у вигляді перетворюючих категорій;

• розроблений метод використання категоріальних систем для побудови й аналізу категорних перетворювачів;

• вирішено ряд відкритих проблем в теорії мовних перетворювачів, схем програм, формальних граматик та мов:

доведена розв'язуваність проблеми еквівалентності детермінованих магазинних автоматів;

доведено існування скінченного несинхронного перетворювача, що відображає одну регулярну множину на іншу (проблема Гінзбурга–Хіббарда);

доведена розв'язуваність проблеми: чи є детермінована мова LR(0)-мовою;

доведено, що для LА(1)-розпізнавачів розв’язувана проблема функціональної еквівалентності;

розв'язувана проблема еквівалентності LR(0)-граматик та LR(1)-граматик, які задають детерміновані контекстно-вільні мови;

доведено, що проблема еквівалентності рекурсивних схем програм без константних функцій розв'язувана;

доведено, що для унарних рекурсивних схем програм (схеми де Баккера–Скотта) проблема функціональної еквівалентності розв'язувана;

• запропоновані й досліджені нові форми подання різних класів мовних перетворю--вачів у вигляді М-систем, семантично-контекстних граматик (СК-грама-ти-ки), перетворюючих та узагальнених перетворюючих граматик;

• розроблені алгоритми аналізу і синтезу мовних перетворювачів, заданих у формі магазинних перетворювачів з додатковими регістрами різної форми, та доведена еквівалентність отриманих перетворювачів з відповідними трансформуючими граматиками;

• розроблено метод алгебраїчного подання процесу проектування складних систем (систем автоматизованого управління) з використання мови L-структур;

• розроблено метод структурно-функціонального проектування для розкладан--ня функцій, що входять в опис проектованих систем.

Отримали подальший розвиток

• дослідження обчислюваних категорій та функторів (нерозв'язуваність низки проблем щодо цих структур);

• аналіз скінченних перетворювачів, що відображають одну регулярну мову в іншу – використано новий метод доведення;

• проблема еквівалентності суворих детермінованих магазинних автоматів;

• формалізація та розвиток створення автоматизованих систем на базі використання принципу модифікуючого моделювання як засобу проектування складних систем за існуючим аналогом;

• розробка мови L-структур, який використовується для опису інформації при проектуванні складних систем;

• формальні схеми опису рівнів проектування складних систем.

Практичне значення отриманих результатів. Отримані в роботі результати представляють інтерес як методологічна основа нового підходу, пов'язаного з послідовним формуванням перетворювачів інформації, дослідженням складних проблем дискретної інформатики. Запропонований в дисертації підхід служить базою, на якій може будуватися теорія, пов'язана з перетворенням дискретної інформації, зокрема із загальними схемами подання процесів перетворення інформації.

Крім того, розроблені методи стали основою для отримання конкретних результатів в різних областях теорії мов і мовних перетворювачів, що дозволило зробити наступні кроки у дослідженні та вирішенні наукових проблем у різних областях інформатики: теорії формальних мов, схем програм, теорії автоматів і перетворювачів. Вирішення відкритих проблем завжди є початком нових розробок.

Апробація результатів дисертації. Матеріали дисертації доповідалися на Всесоюзній конференції зі структурно-математичних методів моделювання мови (Київ, 1970); на Другій всесоюзній конференції з проблем теоретичної кібернетики (Новосибірськ, 1971) ; на Всесоюзному симпозіумі "Теорія мов і методів побудови систем програмування" (Алушта, 1972) ; на Всесоюзному семінарі "Методи і моделі в задачах управління виробництвом" (Таллін, 1979) ; на Міжнародному семінарі ІФАК "Автоматизація проектування систем управління" (Баку, 1980) ; на Восьмій всесоюзній нараді з проблем управління, (Таллін, 1980) ; на семінарі "Технологія програмування інструментальні комплекси створення АСУ" (Миколаїв, 1980) ; на Всесоюзній нараді "Методологія проектування АСУП" (Таллін, 1980) ; на Другій всесоюзній конференції "Системні дослідження проблем управління якістю та автоматизації процесів управління якістю" (Львів, 1981) ; на конференції "Проблеми проектування і створення ВЦ КП і розвитку АСУ" (Душанбе, 1983) ; на Всесоюзній конференції з проблем ОГАС, РАСУ і АСУ, (Канів, 1983), на Галузевій науково-технічній конференції "Основні напрямки розвитку ІАСУ галузі" (Миколаїв, 1983) ; на ІІ республіканській школі-семінарі "Математична теорія систем та прикладні дослідження" (Київ, 1984) ; на школі-симпозіумі "Системологія: системні та міждисциплінарні дослідження", (Ворохта, 1984) ; на VII республіканській науково-практичній конференції ТРСР (Ашхабад, 1984) ; на семінарі "Проблеми підвищення ефективності АСУ і створення систем управління ГАП" (Миколаїв, 1984) ; на Всесоюзній конференції "Автоматизація проектування систем управління" (Єреван, 1984) ; на семінарах Наукової ради з проблем "Кібернетика", в інститутах АН СРСР і АН УРСР з 1980 по 2008 рік.

Публікації. За результатами виконаних досліджень опубліковано 38 наукових робіт: препринти - 2, статті - 28 (у наукових журналах - 13, у збірниках -14, депоновано - 1), тез конференцій - 8.

Особистий внесок здобувача в спільні роботи розподіляється таким чином. Нумерація за списком праць за темою дисертації, наведеним в авторефераті. В роботах [22, 31] здобувачу належить ідея визначення й використання обчислювальної категорії, доведення основної теореми про алгоритмічну нерозв'язуваність існування функтор-но-го морфізму; [28, 29] – здобувачем розроблено мовне подання та загальна схема декомпозиції функцій при їх послідовному розкладанні у процесах структурно-функціонального проектування; [18–21] – здобувачу належить побудова загального вигляду М-системи, які мають декілька видів пам'яті, формулювання напрямків їх використання в задачах мовного перекладу та доведення відповідних теорем; [23–24, 32] – здобувачем розроблені мате-матичні моделі, які використовувались при створенні систем автоматизації проектування, а також метод структуризації процесу побудови автоматизованої системи на різних кроках проектування; [25] – здобувачем був створений метод функціональної декомпозиції, побудований на використанні семантики, яка визначає функції, що підлягають декомпозиції; [26–27] – здобувач розробив викладену в дисертації математичну модель для подання послідовних операцій під час використання методу модифікуючого

моделювання.

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

ОСНОВНИЙ ЗМІСТ РОБОТИ

У «Вступі» подано обґрунтування актуальності теми дослідження, теоретична та практична цінність розглянутої тематики, описані основні наукові результати, отримані здобувачем, їх новизна і місце в розглянутому напрямку досліджень. Виділено коло основних задач, визначена методика досліджень, напрямки використання отриманих результатів.

У першому розділі "Основні конструкції формальних мовних схем" представлено аналітичний огляд стану проблем і досліджень за темою дисертації та обгрунтована необхідність попереднього вирішення декількох груп проблем, необхідних для ефективного використання запропонованих категорних представлень для класу задач, пов'язаних з формальними мовами.

Перша група проблем - це використання теоретико-категорних схем для подання синтаксису та семантики формальних мов, автоматів і перетворювачів. Мова L розглядається як підмножина елементів моноїда Д*, де сам моноїд – це алфавіт цієї мови. Над цією підмножиною визначається категорія EL(Ц), об'єкти якої – слова мови L, а морфізми визначаються за допомогою операцій, які належать заданій множині Ц. Ця категорія називається вузьким сімейством мов L. Синтаксична структура мови L задається за допомогою синтаксичного функтора з категорії EL(Ц) в категорію типів (S-функтор). Доведено, що в такий спосіб може бути представлена будь-яка мова, яка задається граматикою типу нуль за класифікацією Хомського. Цей результат визначається наступною теоремою 2 (подана далі нумерація теорем збігається з їх нумерацією в дисертації).

Теорема 2. Нехай G – граматика типу 0 у класифікації Хомського, а L(G) – породжувана нею мова. Для граматики G існує вузьке сімейство EL(Ц), категорія типів та S-функтор FS з EL(Ц) в категорії типів такі, що задана S-функтором FS мова LT збігається з мовою L(G).

З використанням категорії EL(Ц) та довільної семантичної категорії за допомогою семантичного функтора (С-функтор) з категорії EL(Ц)в семантичну категорію SM визначається семантика мови LT. В залежності від вибору семантичної категорії та С-функтора для однієї й тієї ж мови можна визначати різні семантики. У роботі визначена семантична категорія, об'єкти якої – множини слів, що задані
в алфавіті, який включає як термінальні символи, так і змінні. Морфізми семантичної категорії визначаються виразами, що дозволяють складати систему рівнянь,
рішення якої є кообласть відповідного морфізму. Як приклад показано, як побудувати семантичні категорії та функтори, щоб у цьому вигляді представити відомі схеми, що задають атрибутивну й ініціальну семантики.

Використання семантичного функтора з вузького сімейства в семантичну категорію, яка називається категорією пам'яті, визначає категорний автомат A, який
з мови L виділяє мову L, слова якої мають заздалегідь визначену семантику. Синтаксична категорія у вигляді вузького сімейства визначає будову кожного слова мови L. Приймається припущення, що семантика такого слова прив'язана до синтаксичної структури, а цю семантику можна визначити, побудувавши відповідний семантичний функтор. Якщо об'єкти семантичної категорії визначені як класи еквівалентності на множині слів, які за припущенням можуть зберігатися у відповідному запам'ятаючому пристрої, то така семантична категорія називається категорією пам'яті.

Доведено, що для вузького сімейства з системою операцій Ф, яка є L'-зануре-ною та L-повною, можна побудувати категорний автомат, що виділяє мову L з L' .

У роботі для категорних автоматів визначені умови існування категорій пам'яті зі скінченною кількістю об'єктів. Якщо задати категорію L-сімейств, то ій відповідає категорія категорних автоматів. Таким чином, існує зв'язок між різними мовами, які визначаються одним L-сімейством, та категорними автоматами, зіставленими цим сімействам. Кожен категорний автомат може розглядатися як деякий перетворювач мови L, для якого семантика визначається ствердженням: належить чи не належить вибране слово мові L .

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

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

Якщо, кількість об'єктів прямої границі категоріальної системи K скінченна, то проблема П-еквівалентнос-ті розв'язувана.

Таким чином, аналізуючи загальну кількість об'єктів прямої границі категоріальної системи, яка будується для порівняння двох автоматів, можна отримати висновок, що існує прямий зв'язок між існуванням скінченної прямої границі категоріальної системи та розв'язуваністю проблеми еквівалентності цих автоматів. У четвертому розділі цей метод використовується для вирішення конкретної проблеми – проблема еквівалентності детермінованих магазинних автоматів, для якої доведено, що вона є розв'язуваною.

Для того щоб в алгебраїчних моделях, які розглядаються в дисертації, можна було застосовувати поняття ефективності, при чому для тих розробок, які будуть використовуватися у подальшому, в категорійні моделі додатково введено поняття обчислюваності. Категорні схеми використовують теорію рекурсивних функцій, визначаючи обчислювальні категорії та функтори з додатковими умовами. Для цього нумеруються множини об'єктів та морфізмів і вимагається обчислюваність функцій, які визначають композицію морфізмів та дію морфізму на об'єкт. Відповідно визначаються обчислювані функтори, для яких доведено нерозв'язуваність декількох проблем: існування обчислюваного функторного морфізму, існування спряженості обчислюваних функторів, еквівалентності та ізоморфізму обчислювальних категорій.

Поняття обчислюваності в поєднанні з категоріальними моделями мовних структур створює ще один напрямок вирішення класичних проблем існування алгоритмів, пов'язаних з розв'язуваністю чи нерозв'язуваністю проблем, які виникають при порівнянні мов.

Розділ 2 "Перетворюючі категорії та скінченні перетворювачі" присвячений розгляду проблем, пов'язаних з існуванням скінченних перетворювачів та можливістю використання семантичних функторів для завдання обмежених класів мов.

Скінченний мовний перетворювач – це скінченний автомат з виходом. Він має скінченну кількість станів та перетворює вхідне слово, яке належить мові LA, в вихідне слово, яке належить мові LB. Перетворювач послідовно на кожному кроці зчитує вхідне слово – літера за літерою та видає частини вихідного слова. Розглядаються два типи скінченних перетворювачів – синхронні та несинхронні. Перші перетворюють вхідне слово у вихідне, читаючи вхідну літеру та замінюючи її вихідною. Інші – несинхронні – перетворюють кожну вхідну літеру в ціле слово на виході, можливо і пусте.

Виникає проблема: як побудувати для пари мов відповідний перетворювач, який слова однієї мови перетворює в слова іншої. Навіть для таких досить простих пари мов, як пара регулярних подій, створення зазначених перетворювачів є досить складною задачею. Для дослідження цих проблем в дисер-тації запропонований новий метод: послідовна побудова по парі регулярних мов категорій особливого вигляду. Це спеціальний клас категорій – скінченні перетворюючі категорії. Метод заснований на побудові таких категорій за допомогою системи операцій над ними, які можуть бути організовані у процедуру Р, відповідно до загальної схеми порівняння категорних автоматів, яку запропоновано у першому розділі дисертації.

Доведено, що для кожного скінченного перетворювача Р, який відображає кожне слово х з множини слів UA у слово у з множини слів UB, існує скінченна перетворююча категорія, в якій з парою слів () поєднаний морфізм , що відображає об’єкт в об’єкт . Більше того, доведено, що для скінченного перетворювача Р можна побудувати відповідну скінченну перетворюючу категорію та навпаки, для кожної скінченної перетворюючої категорії можна побудувати відповідний скінченний перетворювач (теореми 17 та 18).

Використовуючи перетворюючі категорії, досліджується проблема існування синхронних перетворювачів, які для пари регулярних подій UA, UB визначають: чи існує відображення UA в UB та UA на UB. Запропонований алгоритм, який по регулярних виразах UA, UB будує відповідну категоріальну систему зі скінченною кількістю об'єктів, що доводить розв'язуваність проблеми існування синхронного перетворювача, який відображує UA в UB. Подальше розширення запропонованого методу дозволяє довести розв'язуваність проблеми існування синхронного перетворювача, який відображує UA на UB. Таким чином, посилено результат роботи
С. Гінзбурга та Г. Хіббарда, оскільки запропонований в дисертації алгоритм дозволяє дати точні оцінки загальної кількості кроків, за яку може бути вирішена проблема існування перетворювача.

Запропонований метод, пов'язаний з побудовою скінченної перетворюючої категорії, був використаний для вирішення відкритої проблеми, поставленої в вищезгаданій роботі С. Гінзбурга та Г. Хіббарда: чи існує для пари регулярних виразів UA, UB скінченний перетворювач P, який несинхронно відображає UA на UB . Розроблено алгоритм побудови перетворюючої категорії, для якої існує такий перетворювач. Алгоритм включає завдання відповідної процедури П у вигляді системи операцій, за допомогою яких послідовно будуються окремі перетворюючі категорії, та схему побудови відповідної категоріальної системи, яка ці категорії об’єд-нує. Щодо цієї системи, то доведено існування та скінченність її прямої границі. Цей алгоритм вирішує проб-лему існування перетворювача.

Кожен перетворювач можна розглядати як реалізацію семантичного функтора, який визначає семантику мови UA, що виражена у мові UB . Ця реалізація дає до-даткову інформацію, яка може бути використана при аналізі мов UA. Тому можна конструювати мови, задаючи відповідні граматики, в яких використовуються до-датково до синтаксичних і семантичні ознаки.

Синтаксичний функтор задає структуру схеми, покладеної в основу створення визначеної мови, а семантичний функтор задає семантику її слів, визначаючи розбиття на класи слів: до одного класу належать слова, які мають однакову семантику. В дисертації визначений та досліджений новий клас граматик – семантично-контекстні граматики (СК-граматики), у конструкцію яких разом з синтаксичним входить семантичнй функтор, і які одночасно породжують пару мов – СК-пару. Перший компонент СК-пари – це частина мови, визначеної S-функтором, яка має непусту семантику при її відображенні семантичним функтором, а другий компонент – це семантика першого компонента. Можна довести наступну теорему.

Теорема 25. Для кожної рекурсивно перелічуваної множини існує контекстно-вільна мова , визначена -функтором , регулярна мова , визначена семантичною категорією SM, та С-функтор SR : SM , такі, що перший компонент СК-пари () збігається з множиною .

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

Якщо розглядати семантичні категорії, об'єктами яких є множини, а морфізмами – відношення на цих множинах, то отримуємо підклас СК-граматик –
СМ-граматики. Доведено зв'язок СК-граматик з РG-граматиками, розглянутими Стірнзом і Льюісом, та можливість вивчення цих граматик методами визначення відповідних семантичних функторів.

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

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

Об'єднуючи синтаксичні правила визначення перетворювача з операціями над пам'яттю, обумовленими відповідною логічною умовою їх використання, отримуємо М-сис-те--му, що одночасно є і синтаксичним аналізатором, і безпосереднім перет-ворюва-чем однієї мови в іншу. Для формування та обчислення логічних умов в М-систе-мах використовуються різні конструкції, які пов'язані зі схемами пам'яті, введеними при тео-ретичному розгляді мовних проблем – скінченними множинами станів, магазинами, чергами, стеками та ін. У цьому плані можуть розглядатися
й категорні автомати з відповідною категорією пам'яті. У дисертації подано загальне визначення М-системи як граматичне завдання деякого мовного перетворювача.

Кожна М-система складається зі скінченної множини зазначених правил, які мають вигляд

M; ,

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

Кожна М-система загального вигляду задає деяке відношення розмірністю на множинах слів, яке зветься перетворенням, визначаючи можливість переходу від початкових р слів , записаних на вхідних стрічках, до слів , які отримуємо на вихідних стрічках.

Теорема 35. Для кожної М-системи MA, яка задає перетворення , існує обчислювана діаграма

де E – вузьке L-сімейство, TУ , TД – категорії типів, SK – семантична категорія,
TУ , TД – -функтори, а S – С-функтор, причому мови LУ, LД , що задані відповідно функторами TУ та TД, збігаються з проекціями перетворення

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

Спочатку в дисертації розглядається найбільш простий випадок трансформуючої граматики (мовного перетворювача), яка задає відношення простого прямого синтаксичного перекладу (ППС-переклад). Побудовані алгоритми, котрі за граматикою такого виду синтезують перетворювач у вигляді М-системи, яка використовує одномагазинну пам'ять (ТСМ-граматика) та реалізує простий прямий переклад, і навпаки, по М-системі синтезують відповідну граматику.

Розглянуті можливі модификації цих алгоритмів, пов’язані з різними виглядом та правилами дії синтезованої М-системи. Такі модифікації дозволяють оптимізувати отримані М-системи, скорочуючи їх допоміжні алфавіти чи кількість правил, які входять у визначення М-системи.

Граматики цього типу можуть використовуватися для аналізу проблем перекладу в формальних мовах. Доведена розв'язуваність відкритої проблеми: чи допускає довільна трансформуюча граматика лічено-неоднозначний переклад?

Теорема 39. Для кожної М-системи , визначеної перетворюючою граматикою , розв’язувана проблема: чи допускає лічено-неоднозначний переклад.

У роботі виділений підклас М-систем та відповідних граматик, еквівалентних мовам, що допускаються однолічильними автоматами.

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

Введення такої пам'яті дозволяє побудувати М-системи, які реалізують прямий синтаксичний переклад. У цих системах використовується додаткова пам'ять у вигляді додаткових регістрів, доданих до основного магазину. Розроблені алгоритми аналізу і синтезу таких М-систем. Доведено, що для кожної граматики, яка реалізує прямий синтаксичний переклад, існує М-система з додатковими регістрами, що представляє перетворювач, і також реалізує цей переклад. Навпаки, для кожного перетворювача у вигляді М-системи з додатковими регістрами можна ефективно побудувати трансформуючу граматику, що породжує цей же переклад.

Оскільки використання додаткових регістрів потребує додаткової пам'яті при їх реалізації на комп'ютері, може бути необхідність скоротити кількість таких регістрів. Побудовані модифікації основного алгоритму синтезу М-системи, пов'язані з перетворенням виразів, які входять в трансформуючу граматику, на основі аналізу відповідної групи підстановок. Винайдені умови, при виконанні котрих кількість додаткових регістрів може бути зменшена. Ці умови визначаються використанням підстановок, що розкладаються. Побудований алгоритм відповідного зменшення числа додаткових регістрів.

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

Введені та досліджені більш складні трансформуючі граматики – узагальнені трансформуючі граматики, які частково представляють схеми універсального перекладу. У цих граматиках зв'язок між парами слів, які визначають схему перекладу, задається відношеннями, які є складовою частиною кожного правила граматики. Тоді під час перекладу, визначеному цими граматиками, можлива одночасна заміна декількох змінних, які визначають вихідне слово, однаковим словом, яке відповідає одній змінній у вхідному слові. Такі граматики визначають новий тип мовних перетворювачів – зв'язані магазинні перетворювачі. Встановлені умови зв’язку між трансформуючими граматиками та різними класами узагальнених трансформуючих граматики (УТГ).

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

Виконаний аналіз різних типів узагальнених трансформуючих граматик, який посилює відомі результати К. Чулика.

Четвертий розділ "Проблема еквівалентності детермінованих магазинних автоматів" присвячений використанню запропонованих вище методів дослідження та порівняння категорних автоматів до вирішення відкритої проблеми, поставленої ще в 1965 році: чи можна для двох детермінованих магазинних автоматів (ДМА) розв'язати проблему їх еквівалентності, тобто вирішити: збігаються чи не збігаються представлені цими автоматами мови?

Загальна схема порівняння автоматів була визначена в підрозділі 1.3. Вона базується на побудові категоріальної системи та аналізі її прямої границі. Тоді вирішення конкретної проблеми еквівалентності ДМА розпадається на декілька етапів.

По-перше, необхідно розробити алгоритм створення ДМА у вигляді категорного автомата, щоб потім порівняти між собою пару відповідних ДМА категорних автоматів.

По-друге, для порівняння відповідних множин морфізмів потрібен засіб їх опису в залежності від пар об'єктів, з якими ці морфізми пов'язані. Для цього використовується подання у вигляді системи умовних рівнянь. Далі ця система буде використовуватися для побудови категоріальної системи K , яка визначається за допомогою операцій процедури Р. Для різних процедур отримуємо різні категоріальні системи. Тому велика частина успішного розв’язання проблеми полягає в тому, щоб вибрати таку систему операцій, яка б була достатньою для автоматів, що по-рівнюються. При цьому бажано, щоб операції процедури були коректними, тобто вони не повинні змінювати рівні множини морфізмів на нерівні чи, навпаки,
нерівні на рівні. З іншого боку, операції процедури Р мають бути такими, щоб ряд категорій, який визначає категоріальну систему, внаслідок застосування процедури Р перетворився з нескінченного в скінченний. У цьому випадку можна довести розв'язуваність проблеми еквівалентності автоматів.

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

У категорних автоматах, що порівнюються, кожному слову відповідає деякий морфізм, а порівняння слів розглядається як порівняння цих морфізмів. Вихідною гіпотезою є припущення, що множини морфізмів, поставлених у відповідність мовам, що порівнюються, збігаються. Саме припущення формально записується у вигляді рівнянь, в яких використовуються вирази, що включають символи вхідного алфавіту та змінні виду , кожна з яких представляє деяку множину морфізмів. За допомогою процедури Р послідовно створюються нові вирази та нові рівняння. Треба довести, що всі пари множин морфізмів, які отримані внаслідок застосування процедури Р, збігаються, або ж знайти існуючу невідповідність між множинами морфізмів, яка спростовує вихідне припущення.

У дисертації розроблена така процедура Р у вигляді системи операції над множинами морфізмів. Операції процедури Р використовувалися для послідовної побудови категоріальної системи K. Стосовно операцій процедури Р було доведено, що більшість операцій процедури Р є коректними, тобто вони не порушують рівність чи нерівність тих множин морфізмів, до яких вони застосовуються. Некоректною може бути тільки одна з операцій процедури Р – операція підстановки. Але її особливість в тому, що вона не переводить нерівні рівняння в рівні. На основі процедури Р побудований алгоритм порівняння автоматів.

Використовуючи цей алгоритм при побудові категоріальної системи, спочатку доведено, що розв'язуваною є проблема еквівалентності суворих детермінованих магазинних автоматів. Це був відомий результат, але доведений методом побудови категоріальної системи та аналізу її прямої границі, який був запропонований в дисертації. Потім доведено, що проблема еквівалентності розв'язувана і тоді, коли існує один магазинний символ, який називається особливим та видаляється з пам'яті ДМА пустим словом. Це вже новий результат. Вся складність аналізу у цьому випадку полягає в тому, що в разі існування особливого символу довжина послідовності символів, які зберігаються у магазині, може нескінченно зростати. Тобто, на жаль, не має безпосереднього зв’язку між довжиною послідовності, яка зберігається у магазині, та довжиною слова, яке аналізується магазинним автоматом, як це існує у суворих ДМА.

Щоб вийти з цього становища, у процедуру Р включається додаткова операція, яка дозволяє скорочувати послідовності з особливих символів. Показано, що існує скінченне число , яке в сукупності обмежує можливу довжину -послідов-ностей, що складаються з особливих символів та є складовою частиною послідовностей магазинних символів, які утворюються при порівнянні двох ДМА, магазинні алфавіти яких включають особливий символ. А це доводить скінченність процесу побудови категоріальної системи для цього випадку.

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

Теорема 54. Нехай A та B – два детермінованих магазинних автомати, а K – категоріальна система, побудована за допомогою алгоритму порівняння з начальної категорії К0 . Тоді, якщо при побудові K для всіх перехід від Кi до Ki+1 були коректними, то проблема еквівалентності автоматів A та B розв’язувана.

Однак можливий варіант, коли внаслідок алгоритму порівняння отримано слово, що обумовлює нерівність одного з умовних рівнянь, які використовувалися при побудові категоріальної системи. Тоді знайдене слово перевіряється на приналежність кожній з порівнюваних мов. Якщо воно належить тільки одній мові, нееквівалентність автоматів доведена самим існуванням цього слова.

Але, коли воно належить обом мовам, існування цього слова означає,