The definition of formal languages in the meta language of normal forms of knowledge
The expressive means of the metalanguage of normal forms of knowledge in relation to different level formal languages are investigated. The formal descriptions of a multitude of linguistic examples are given. The graphic metadescription equivalent to the given text description of the interpreter of...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/309 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-309 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/97/c12f6ce9cee2ae817bf980744cdf4697.pdf |
| spelling |
pp_isofts_kiev_ua-article-3092024-04-28T11:45:31Z The definition of formal languages in the meta language of normal forms of knowledge Определение формальных языков в метаязыке нормальных форм знаний Визначення формальних мов у метамові нормальних форм знань Kurgaev, A.F. Grygoryev, S.M. meta-language; regular languages; context-free languages; context languages; 0-languages; Turing machines; formal description of languages UDC 004.8 метаязык; регулярные языки; контекстно-свободные языки; контекстные языки; 0-языки; машины Тьюринга; текстовое и графическое описания языка УДК 004.8 метамова; регулярні мови; контекстно-вільні мови; контекстні мови; 0-мови; машини Тьюринга; текстові й графічні описи мов УДК 004.8 The expressive means of the metalanguage of normal forms of knowledge in relation to different level formal languages are investigated. The formal descriptions of a multitude of linguistic examples are given. The graphic metadescription equivalent to the given text description of the interpreter of the universal Turing machine is developed. The description provided of the universal Turing machine interpreter can be applied to solving the task of modelling the behavior of any T-machine (which performs the task of data conversion on its memory tape). The formal definition of the translator of the determined Turing machine is given. The ability to describe in the metalanguage of normal forms of knowledge the interpreting-translating and the translating-translating processes of formulating and solving of a given task, for which a solution exists is substantiated and defined.Problems in programming 2017; 4: 037-050 Исследованы выразительные возможности метаязыка нормальных форм знаний по отношению к формальным языкам разного уровня. Даны формальные описания множества лингвистических примеров. Разработано графическое метаописание интерпретатора универсальной машины Тьюринга, эквивалентное приведенному текстовому описанию. Представленное определение интерпретатора универсальной машины Тьюринга может быть применено для решения задачи моделирования поведения любой Т-машины (решающей задачу преобразования данных на ее ленте памяти). Дано формальное определение транслятора детерминированной машины Тьюринга. Обоснована и определена возможность описания в метаязыке нормальных форм знаний интерпретирующе-транслирующего и транслирующе-транслирующего процессов постановки и решения произвольной задачи, имеющей решение.Problems in programming 2017; 4: 037-050 Досліджено виразні можливості метамови нормальних форм знань стосовно формальних мов різного рівня. Дано формальні описи множини лінгвістичних прикладів. Розроблено графічне метавизначення інтерпретатора універсальної машини Тьюринга, еквівалентне наведеному текстовому опису. Представлене визначення інтерпретатора універсальної машини Тьюринга може бути застосоване для розв’язку задач моделювання поведінки будь-якої Т-машини (яка вирішує задачу перетворення даних на її стрічці пам’яті). Дано формальне визначення транслятора детермінованої машини Тьюринга. Обґрунтовано й сформульовано можливість опису в метамові нормальних форм знань інтерпретуюче- транслюючого й транслююче-транслюючого процесів постановки й розв’язку довільної задачі, що має розв'язок.Problems in programming 2017; 4: 037-050 Інститут програмних систем НАН України 2018-11-15 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/309 10.15407/pp2017.04.037 PROBLEMS IN PROGRAMMING; No 4 (2017); 37-50 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2017); 37-50 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2017); 37-50 1727-4907 10.15407/pp2017.04 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/309/304 Copyright (c) 2018 PROBLEMS OF PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:45:31Z |
| collection |
OJS |
| language |
rus |
| topic |
meta-language regular languages context-free languages context languages 0-languages Turing machines formal description of languages UDC 004.8 |
| spellingShingle |
meta-language regular languages context-free languages context languages 0-languages Turing machines formal description of languages UDC 004.8 Kurgaev, A.F. Grygoryev, S.M. The definition of formal languages in the meta language of normal forms of knowledge |
| topic_facet |
meta-language regular languages context-free languages context languages 0-languages Turing machines formal description of languages UDC 004.8 метаязык регулярные языки контекстно-свободные языки контекстные языки 0-языки машины Тьюринга текстовое и графическое описания языка УДК 004.8 метамова регулярні мови контекстно-вільні мови контекстні мови 0-мови машини Тьюринга текстові й графічні описи мов УДК 004.8 |
| format |
Article |
| author |
Kurgaev, A.F. Grygoryev, S.M. |
| author_facet |
Kurgaev, A.F. Grygoryev, S.M. |
| author_sort |
Kurgaev, A.F. |
| title |
The definition of formal languages in the meta language of normal forms of knowledge |
| title_short |
The definition of formal languages in the meta language of normal forms of knowledge |
| title_full |
The definition of formal languages in the meta language of normal forms of knowledge |
| title_fullStr |
The definition of formal languages in the meta language of normal forms of knowledge |
| title_full_unstemmed |
The definition of formal languages in the meta language of normal forms of knowledge |
| title_sort |
definition of formal languages in the meta language of normal forms of knowledge |
| title_alt |
Определение формальных языков в метаязыке нормальных форм знаний Визначення формальних мов у метамові нормальних форм знань |
| description |
The expressive means of the metalanguage of normal forms of knowledge in relation to different level formal languages are investigated. The formal descriptions of a multitude of linguistic examples are given. The graphic metadescription equivalent to the given text description of the interpreter of the universal Turing machine is developed. The description provided of the universal Turing machine interpreter can be applied to solving the task of modelling the behavior of any T-machine (which performs the task of data conversion on its memory tape). The formal definition of the translator of the determined Turing machine is given. The ability to describe in the metalanguage of normal forms of knowledge the interpreting-translating and the translating-translating processes of formulating and solving of a given task, for which a solution exists is substantiated and defined.Problems in programming 2017; 4: 037-050 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/309 |
| work_keys_str_mv |
AT kurgaevaf thedefinitionofformallanguagesinthemetalanguageofnormalformsofknowledge AT grygoryevsm thedefinitionofformallanguagesinthemetalanguageofnormalformsofknowledge AT kurgaevaf opredelenieformalʹnyhâzykovvmetaâzykenormalʹnyhformznanij AT grygoryevsm opredelenieformalʹnyhâzykovvmetaâzykenormalʹnyhformznanij AT kurgaevaf viznačennâformalʹnihmovumetamovínormalʹnihformznanʹ AT grygoryevsm viznačennâformalʹnihmovumetamovínormalʹnihformznanʹ AT kurgaevaf definitionofformallanguagesinthemetalanguageofnormalformsofknowledge AT grygoryevsm definitionofformallanguagesinthemetalanguageofnormalformsofknowledge |
| first_indexed |
2024-09-25T04:02:55Z |
| last_indexed |
2024-09-25T04:02:55Z |
| _version_ |
1818526259533053952 |
| fulltext |
Формальні методи розробки програмного забезпечення
© А.Ф. Кургаев, С.Н. Григорьев, 2017
ISSN 1727-4907. Проблеми програмування. 2017. № 4 37
УДК 004.8
А.Ф. Кургаев, С.Н. Григорьев
ОПРЕДЕЛЕНИЕ ФОРМАЛЬНЫХ ЯЗЫКОВ
В МЕТАЯЗЫКЕ НОРМАЛЬНЫХ ФОРМ ЗНАНИЙ
Исследованы выразительные возможности метаязыка нормальных форм знаний по отношению к фор-
мальным языкам разного уровня. Даны формальные описания множества лингвистических примеров.
Разработано графическое метаописание интерпретатора универсальной машины Тьюринга, эквива-
лентное приведенному текстовому описанию. Представленное определение интерпретатора универ-
сальной машины Тьюринга может быть применено для решения задачи моделирования поведения лю-
бой Т-машины (решающей задачу преобразования данных на ее ленте памяти). Дано формальное опре-
деление транслятора детерминированной машины Тьюринга. Обоснована и определена возможность
описания в метаязыке нормальных форм знаний интерпретирующе-транслирующего и транслирующе-
транслирующего процессов постановки и решения произвольной задачи, имеющей решение.
Ключевые слова: метаязык, регулярные языки, контекстно-свободные языки, контекстные языки,
0-языки, машины Тьюринга, текстовое и графическое описания языка.
Введение
Для определения языков использу-
ют формальные грамматики, которые за-
дают четверкой
G <VT, VN, S, P>,
где VT и VN – непересекающиеся терми-
нальный и нетерминальный алфавиты; S –
аксиома, начальный символ; P – конечная
система правил подстановки. Каждой
грамматике G однозначно соответствует
анализируемый (или порождаемый) язык
)(GL .
В зависимости от выразительных
возможностей различают четыре уровня
грамматик (и языков) с номерами от 3 до 0
в порядке возрастания их общности: авто-
матные (или регулярные), контекстно-
свободные (КС), далее – контекстные (или
НС-грамматики) и на вершине иерархии –
уровня 0 и соответствующие им машины
Тьюринга.
Множество G грамматик G G с
единообразным набором структур правил
множества P оформляют в некоторый ме-
таязык для определения синтаксиса объ-
ектных (описываемых) языков использо-
ванием некоторого количества правил.
Среди известных метаязыков наиболее по-
пулярны BNF (Backus-Naur Form) и
Extended (расширенный) BNF [1].
Однако, в качестве языка представ-
ления знаний метаязык EBNF (и все дру-
гие известные метаязыки) имеет опреде-
ленные недостатки. В частности, создан-
ный первично для узкоспециальных целей
и такой, что хорошо их обеспечивает, он
не является функционально полным и по-
тому не пригоден для представления про-
извольных знаний.
В работе [2] предложен и в [3, 4]
описан метаязык нормальных форм знаний
(НФЗ), развивающий выразительные сред-
ства EBNF. Для достижения функциональ-
ной полноты в метаязык EBNF введены:
отношение отрицания, приме-
нимое к любому понятию в описании (обо-
значается знаком ^, предшествующим
имени отрицаемого понятия);
три элементарных операции
над информационными структурами: рас-
познавание, распознавание со следом и
порождение, обозначаются соответственно
знаками ?, # и !, присоединяемыми к име-
ни понятия, вводящему некоторую инфор-
мационную структуру.
Покажем, что для формальных язы-
ков каждого уровня в метаязыке НФЗ есть
адекватные выразительные средства.
1. База знаний в метаязыке НФЗ
Любое описание предметной обла-
сти в метаязыке НФЗ составляется из двух
частей. Первая часть – это информацион-
ная структура множества определений
понятий (нетерминалов), связанных базо-
Формальні методи розробки програмного забезпечення
38
выми отношениями метаязыка НФЗ. Вто-
рая часть состоит из двух подмножеств
терминалов – множества элементарных
процедур и множества элементарных
структур данных, которые реализуют на
одном из языков программирования в
форме единой библиотечной системы.
Каждый из терминалов имеет собственное
имя и в описании информационной струк-
туры используется наравне с нетерми-
нальными понятиями.
Определение 1. База знаний – это
любое замкнутое на предметы предметной
области D определение понятия в форме
информационной структуры, элементами
которой являются понятия, связанные
между собой системой отношений мета-
языка НФЗ, выполнимых на предметной
области D.
Определение 2. Данные – это
предметные значения понятий.
2. Структура области данных
Общую предметную область D зна-
чений понятий представим двумя незави-
симыми массивами – входным (INP) и вы-
ходным (OUT), каждый из них удовлетво-
ряет аксиомам отношения предшествова-
ния [5]:
никакой предмет не предше-
ствует самому себе;
если A предшествует В, а В
предшествует С, то A предшествует С;
если A и В – произвольные
различные предметы, то либо A предше-
ствует В, либо В предшествует A ;
в любом непустом классе пред-
метов имеется первый предмет, то есть
предмет, предшествующий всем осталь-
ным предметам класса.
С массивами INP и OUT свяжем
переменные m и n , принимающие из
множества натуральных чисел значения
текущих координат соответствующих
массивов, и две библиотеки пар процедур
одноименных предикатов – библиотеку
анализа над данными INP и библиотеку
порождения над данными OUT. Перемен-
ные m и n будем считать независимы-
ми, неявно заданными в квантификации
всеобщности, аргументами (указателями
на предметные значения) именованных
понятий базы знаний.
Для каждой процедуры из библио-
теки анализа есть одноименная процедура
в библиотеке порождения и наоборот.
Каждая процедура – это реализация опера-
ционального определения некоторого пре-
диката в форме алгоритма обработки дан-
ных. Как правило, – это структурно про-
стые действия типа сравнения с констан-
той, записи, чтения, арифметические и
другие вычисления.
Каждая процедура библиотеки ана-
лиза согласно своему содержанию:
выполняет некоторое преобра-
зование данных, взятых из массива INP,
начиная с координаты, определяемой зна-
чением переменной m ;
формирует значение истинно-
сти, зависящее от успеха преобразования;
при успехе (истинность – "ис-
тина") модифицирует значение перемен-
ной m , переводя указатель на начало сле-
дующего фрагмента массива INP.
Каждая процедура библиотеки по-
рождения:
порождает некоторый фрагмент
данных в массив OUT, начиная с коорди-
наты, определяемой значением перемен-
ной n;
формирует значение истинно-
сти "истина" и модифицирует значение
переменной n , переводя указатель на
начало следующего свободного фрагмента
массива OUT.
Введем также набор системных
процедур, управляющих этими элемента-
ми пространства данных, в том числе:
RB – всегда истинная процедура
переключения библиотек. После ее выпол-
нения вызов процедуры из библиотеки по-
рождения заменяется вызовом процедуры
из библиотеки анализа и наоборот;
RIO – всегда истинная процедура
переключения массивов данных. После ее
выполнения процедуры из библиотеки
анализа обрабатывают данные из OUT, а
процедуры из библиотеки порождения –
данные из INP;
Формальні методи розробки програмного забезпечення
39
UIO – всегда истинная процедура
объединения / разделения массивов дан-
ных. После однократного ее выполнения
INP обрабатывается как два массива (INP и
OUT) с всегда равными координатами ана-
лиза и порождения. Повторный ее вызов
разделяет массивы.
Процедура RIO переключения мас-
сивов объединяет в единый процесс преоб-
разование данных одного из массивов с
преобразованием данных другого массива.
То, что порождено в OUT, становится до-
ступным для анализа и наоборот, то, что
проанализировано из INP, может быть за-
менено порожденным.
3. Соотношения между языками
для основных форм определения
понятий в метаязыке НФЗ
Формальным языком, заданным на
базовом множестве U, называют всякое
подмножество свободной полугруппы U*,
т. е. множество цепочек из элементов U
(подмножество множества U*), вслед-
ствие чего на формальные языки распро-
страняются теоретико-множественные
операции объединения, умножения, до-
полнения, пересечения, возведения в сте-
пень [6–8]. Согласно теории понятий [9]
любому понятию (наравне с содержанием,
смыслом) присуще множество предмет-
ных значений, составляющее объем поня-
тия. Основываясь на одинаковой (теоре-
тико-множественной) природе объема по-
нятия и формального языка в [10] обосно-
ван ряд утверждений, принятых здесь в
качестве исходных свойств метаязыка
НФЗ.
Утверждение 1. Определение в
форме альтернативы задает язык опреде-
ляемого понятия как объединение языков
понятий определяющей части.
Утверждение 2. Определение поня-
тия в форме последовательности задает его
язык как произведение языков понятий
определяющей части.
Утверждение 3. Определение поня-
тия в форме последовательности двух по-
нятий, одно из которых взято с отрицани-
ем, задает язык определяемого как допол-
нение языка отрицательного до языка по-
ложительного понятия.
Утверждение 4.
а) отрицательное определение лю-
бого понятия в форме альтернативы от-
рицательных понятий задает язык как пе-
ресечение языков понятий, входящих в
альтернативу.
б) определение любого понятия по-
следовательностью двух понятий, одно из
которых взято с отрицанием и задано аль-
тернативой отрицательных понятий, а
другое – положительное, задает язык по-
нятия как пересечение языков понятий,
входящих в определяющую часть альтер-
нативы.
Утверждение 5. Определение лю-
бого понятия в форме итерации другого
понятия задает язык понятия как итера-
цию (операция Клини) языка понятия, вхо-
дящего в определяющую часть.
Так, если понятие с именем A
определено как итерация понятия с име-
нем B :
)(BA ;
то язык AL определен итерацией языка
BL , т. е. произвольной степенью (в том
числе нулевой) языка BL .
Утверждение 6. Язык всякого по-
нятия (с именем А), являющийся ненулевой
степенью языка другого понятия (с име-
нем B ), задается рекурсивным определе-
нием формы:
BABA ;
4. Определение регулярных
языков
Язык является регулярным, если он
задан грамматикой, правила которой име-
ют форму:
xA и/или ByA , допуская
xA А (x, y VT
+; А, В VN ).
Поскольку любая конечная после-
довательность слов выразима конечным
произведением и/или конечной степенью
языков, включающих лишь один символ
Формальні методи розробки програмного забезпечення
40
алфавита VT, то в силу утверждений 1, 5 и
6 справедливо
Утверждение 7. Любой регулярный
язык может быть определен в метаязыке
НФЗ.
Пример 1. Язык [7]:
naL { | }0n ,
определяется итерацией
(L 'а' ).
Пример 2. Язык [7]:
mn baL { | n, m 1},
определяется в форме
L 'а' ('а' ) / 'b' ('b').
В силу замкнутости класса регуляр-
ных языков относительно умножения, объ-
единения, итерации, дополнения, пересе-
чения [6–8] (и, добавим, – ненулевой сте-
пени), справедливо
Утверждение 8. Язык любого по-
нятия, определение которого дано с ис-
пользованием лишь форм, указанных в
формулировках утверждений 1– 6, являет-
ся регулярным.
5. Определение контекстно-
свободных языков
Язык является контекстно-
свободным, если задан КС-грамматикой,
правила которой имеют форму:
A , где А VN, (VN VT )*.
Класс КС-грамматик включает класс
регулярных грамматик в качестве соб-
ственного подкласса и отличается от него
допущением правил с самовставлением не-
терминальных символов (теорема 11 [8]).
В самоопределении метаязыка НФЗ
[4] нет ограничений на самовставление
определяемого понятия, следовательно,
справедливо
Утверждение 9. Любой КС-язык
можно определить в метаязыке НФЗ.
Пример 3. Язык [6, 12]:
nnbaL { | n > 0},
определяется предложением метаязыка
НФЗ в форме альтернативы последова-
тельностей:
L 'а' L 'b' / 'а' 'b' .
Пример 4. Язык [6, 8]:
mnn abaL { | n, m > 0}
определяется в форме:
1) 21 SSL ;
2) 1S 'а' 1S 'b' / 'а' 'b';
3) 2S = 'a' 2S / 'a' .
Утверждение 10. Язык любого по-
нятия, определение которого дано с ис-
пользованием форм, указанных в утвер-
ждениях 1– 6, и форм с самовставлением,
является КС-языком.
6. Определение контекстных
языков
Язык является контекстным (НС-
языком), если задан НС-грамматикой, пра-
вила которой имеют форму:
1 А 2 1 2, где А VN; 1, 2,
(VN VT )* и не пусто.
КС-грамматики составляют под-
класс НС-грамматик при ограничении пра-
вилами с пустым контекстом 1 и 2.
Вследствие незамкнутости КС-
языков относительно операций дополне-
ния и пересечения (теорема 21 [8]), в класс
контекстных включаются языки, заданные
с использованием этих операций над КС-
языками. В силу утверждений 3 – 4 (фор-
мулировка которых не ограничивает слож-
ность языков, над которыми определены
эти операции) справедливо
Утверждение 11. Существуют НС-
языки, для определения которых достаточ-
но теоретико-множественных операций и
форм с самовставлением.
Пример 5. Язык [6–8, 11–13]:
mmm abaL { | m 1}
формально определяется описанием мета-
языка НФЗ, имеющим следующий смысл.
Если первые две (из трех) подцепочки
Формальні методи розробки програмного забезпечення
41
равны по числу символов (контекстное
условие), то первая подцепочка произ-
вольна по длине, а вторая – равна третьей:
1) L ^ 1S ('a') 2S ;
2) ^ 1S = 'a' ^ 1S 'b' / 'a' 'b';
3) 2S = 'b' 2S 'a' / 'b' 'a'.
НС-грамматики занимают проме-
жуточное положение между контекстно-
свободными и самыми общими (0-
грамматиками): в структуре их правил
вместо одного нетерминала слева (как в
КС-грамматиках), хотя и в ограниченном
виде, но уже есть цепочка, поэтому они, не
решая всех проблем формализации языков,
приобретают проблемы реализации 0-
грамматик.
Кроме теоретико-множественных
операций, в теории формальных грамма-
тик для определения языков используется
дерево составляющих [6] (структура со-
ставляющих, С-маркер [12]) конкретного
предложения. С-маркер строится конеч-
ным преобразователем (на его ленте памя-
ти) в процессе вывода предложения по за-
данной грамматике языка. Известно [6, 8],
что С-маркер можно построить для любого
предложения любого КС-языка.
В описанной [3, 4] реализации ме-
таязыка НФЗ операция построения С-
маркера предложения языка некоторого
понятия именуется символом "#" (в тек-
стовом описании присоединяется к имени
понятия) и выполняется процедурой ин-
терпретации с записью показателей струк-
туры в память следа. С-маркер использу-
ется процедурой интерпретации в режиме
порождения – как повторение конечного
процесса вывода предложения. Операция
построения С-маркера является аналогом
логического оператора неопределенной де-
скрипции ("эпсилон-оператора" [9, 14]),
выделяющего конкретный предмет из объ-
ема понятия, к которому он применен.
Множество форм метаязыка НФЗ не
включает определенной дескрипции, назы-
ваемой также "йота-оператором" [9] (рас-
смотренного в [15] определения понятия в
форме равенства предметных значений),
однако она нужна для ассоциативного по-
иска, выражения контекстных условий и
для других целей. Семантику идентично-
сти значения некоторого понятия (с име-
нем N) текущему значению из массива INP
будем выражать (с использованием проце-
дуры RB переключения библиотек) в сле-
дующей общей форме:
A = RB N RB! / ^RB.
Ее смысл состоит в следующем: при
интерпретации понятия с именем A после
выполнения первого терминала RB вызов
любого терминала из одной библиотеки
заменяется вызовом одноименного терми-
нала из другой. Поэтому при порождении
предложения (связанного с понятием N )
выполняется анализ из INP в точности та-
кого же предложения. Если этот анализ
успешен, то выполнение второго термина-
ла RB восстанавливает исходный порядок
вызова терминалов из библиотек и интер-
претация определения понятия A оканчи-
вается со значением истинности "истина",
иначе – "ложь".
Пример 6. Язык [13]:
3{ cbabaL mnmn | n, m 1},
на примере которого доказано существо-
вание НС-языков, не являющихся КС-
языками, формально определяется описа-
нием в метаязыке НФЗ:
1) L 1S 2S # 3S 'c' 'c' 'c' ^'c';
2) 1S = 'a' 1S / 'a';
3) 2S = 'b' 2S / 'b';
4) 3S = RB 1S 2S RB! / ^RB.
Пример 7. Язык [12]:
L = {x x | x – не пустая цепочка из
букв "а", "b"} формально определяется
описанием в метаязыке НФЗ:
1) L 1S RIO 2S # RIO 1S ! 3S ^ 1S / 1S L;
2) 1S = 'а' / 'b';
3) 2S = ( 1S ) ;
4) 3S = RB 2S 1S RB! / ^RB;
Исходная ситуация – в INP не пу-
стая цепочка из букв "а", "b", OUT – пуст;
результат – "истина", если в INP – xx, до-
полнительно – в OUT порождается x.
Формальні методи розробки програмного забезпечення
42
При интерпретации понятия L с
понятием 1S связывается значение первого
символа цепочки из INP, с понятием 2S –
(возможно, пустая) цепочка символов из
OUT, далее значение 1S порождается в
OUT, а интерпретацией 3S проверяется
совпадение конкатенации значений 2S и
1S с текущим значением цепочки из INP:
если совпадает (значение 3S –
истина), то интерпретацией ^ 1S выполня-
ется проверка окончания цепочки и, если
цепочка исчерпана, то успешное заверше-
ние интерпретации понятия L , иначе вы-
полняется вторая альтернатива определе-
ния L – пропускается первая буква теку-
щего значения цепочки и рекурсивное по-
вторение интерпретации понятия L ;
если не совпадает, то формиру-
ется значение 3S – ложь, вследствие чего
выполняется вторая альтернатива опреде-
ления L с пропуском первой буквы теку-
щего значения цепочки и рекурсивным по-
вторением интерпретации понятия L . Ес-
ли же выполнение второй альтернативы
определения L не может быть продолжено
из-за исчерпания цепочки букв, то форми-
руется результирующее значение истинно-
сти ложь.
Рассмотренные общесистемные
операционные средства, определения при-
меров известных НС-языков и отсутствие
контрпримеров обосновывают
Утверждение 12. Всякий НС-язык
можно определить в метаязыке НФЗ.
7. Определение 0-языков
Язык принадлежит уровню 0 (явля-
ется 0-языком), если он задан 0-
грамматикой с использованием правил
" ", ограниченных лишь тем, что и
(цепочки из VNVT) не могут быть пу-
стыми.
Общие системы подстановок уни-
версальны: если существует формальная
процедура задания языка, то его можно
определить 0-грамматикой [6]. Множество
правил 0-грамматики включает КС-
грамматику, с каждой интерпретацией ко-
торой можно связать С-маркер (структуру
составляющих [16] или, в другой термино-
логии, дерево составляющих [6]), множе-
ство трансформаций, каждая из которых
преобразует набор (k, k 1) С-маркеров в
новый С-маркер, и множество правил,
определяющих порядок применения
трансформаций. Среди разновидностей
трансформаций различают присоединение,
перестановки, устранение (или добавле-
ние) элементов собственного анализа, лю-
бую из которых можно применять только к
полностью проанализированной цепочке
[16].
8. Универсальная машина
Тьюринга
Универсальная машина Тьюринга –
это U-машина с фиксированной структу-
рой, имитирующая поведение любой ма-
шины Тьюринга (T-машины).
Для T-машины исходный результат
состоит в том, что если язык L определен
0-грамматикой, то по ней можно построить
T-машину, которая допускает язык L, и
наоборот [16, 17]. Тоесть утверждается од-
нозначное соответствие между 0-языком и
T-машиной. Следовательно, для множе-
ства 0-языков можно построить множе-
ство T-машин.
U-машина отличается тем, что на
ней одной можно моделировать поведение
всего множества T-машин, каждая из ко-
торых допускает некоторый 0-язык, и тем
самым решить произвольную задачу уров-
ня 0, для которой есть решение.
В теории алгоритмов интерпрета-
тор U-машины исследовался столь де-
тально потому, что составляет отдельную
задачу, сложность которой (по определе-
нию) не ниже уровня 0, так как в конеч-
ном итоге, именно интерпретатор решает
произвольную задачу уровня 0 (интерпре-
тируя модель любой T-машины, решаю-
щей задачу уровня 0). В силу этого реали-
зация в некотором языке интерпретатора
U-машины гарантирует достаточность
его выразительных возможностей для
постановки и решения произвольной за-
дачи (для которой есть решение) и,
тем самым, универсальность машины,
реализующей этот язык. А. Тьюринг
предложил и показал способ построения
Формальні методи розробки програмного забезпечення
43
U-машины, М. Минский [18] разработал
форму представления любой T-машины
на ленте U-машины и описал интерпре-
татор U-машины в форме диаграммы
состояний.
Используя эти результаты, для фор-
мализации примем два допущения [19].
1. Пусть полубесконечная вправо
лента U-машины отождествлена с совме-
щенными (после выполнения процедуры
UIO) массивами INP и OUT пространства
данных метаязыка НФЗ и разделена на зо-
ны, расположенные слева-направо в сле-
дующем порядке:
начальное состояние tq неко-
торой произвольной T-машины;
первый, обозреваемый читаю-
ще-записывающей головкой T-машины,
символ ta ;
конечное описание T-машины
(последовательность взаимосвязанных про-
дукций), представленное пятерками iq , ia ,
jq , ja , id – текущее состояние T-машины,
считываемый символ, новое состояние T-
машины, записываемый символ и значение
сдвига (0 – вправо, 1 – влево) читающе-
записывающей головки T-машины соответ-
ственно. Каждая из продукций имеет смысл
выражения: "Если T-машина находится в
состоянии iq и на ее ленте обозревается
символ ia , то заменить его на символ ja и
перейти в состояние jq , в котором выпол-
нить преобразование соседнего (слева или
справа от ia ) символа ленты T-машины".
Каждое состояние iq , jq , tq из множества
Q пусть именуется одним символом лати-
ницы или цифры. Входные символы ia , ja ,
ta пусть принадлежат алфавиту , состав-
ленному из букв латиницы и цифр, а также
включают нулевой код;
разделяющий выделенный сим-
вол Код0;
полубесконечная вправо псев-
долента T-машины содержит конечную
цепочку символов (за ней – нулевые коды),
одно из ее знакомест занято маркером (тот
же выделенный символ Код0), указываю-
щим положение читающе-записывающей
головки T-машины.
2. Положение читающе-записы-
вающей головки U-машины однозначно
определяется значением переменной m
(координаты INP).
В начальный момент: читающе-
записывающая головка U-машины распо-
ложена в крайнем левом положении и обо-
зревает символ, именующий начальное со-
стояние tq T-машины; читающе-записы-
вающая головка T-машины установлена
также в крайнем левом положении ее лен-
ты (маркер Код0 записан в первой клетке
псевдоленты T-машины).
Семантику интерпретатора U-
машины формально определим в метаязы-
ке НФЗ:
1) интерпретация = состояние
символ# (^Код0 ^правило ^преобразовать);
2) ^правило = та_пятерка? состоя-
ние символ сдвиг# / пятерка ^Код0
^правило;
3) та_пятерка = RB состояние
символ RB! / ^RB;
4) пятерка = состояние символ
состояние символ сдвиг;
5) ^преобразовать = (^Код0 пятер-
ка) Код0 (символ ^Код0) ^зап_сдвиг заме-
нить ^чтение? Код0!;
6) ^зап_сдвиг = символ? сдвиг! /
сдвиг!;
7) сдвиг = '0' / '1';
8) заменить = символ ^если_0?
символ! /^если_0? символ!
/^записать_символ;
9) ^если_0 = '0';
10) ^записать_символ = символ?
символ! / символ!;
11) ^чтение = символ#;
База знаний состоит из 16 понятий,
в том числе 11 нетерминалов определяют
состояния U-машины (это число можно
уменьшить до 10, заменив понятие "пятер-
ка" его определяющей частью) и пяти тер-
миналов: RB – переключения библиотек;
"символ", "состояние" – значения из мно-
жеств и Q соответственно; "сдвиг" – зна-
чения из двузначного множества {'0', '1'} и
"Код0" – разделяющий символ или маркер.
В ряду известных определений U-машины,
Формальні методи розробки програмного забезпечення
44
составленных в свое время Икено, Ватанабе
и Минским, данное является наиболее
естественным и простейшим по критерию
К. Шеннона [20].
Графическое метаописание интер-
претатора U-машины показано на рисунке.
Очевидно, что оно эквивалентно приве-
денному текстовому описанию.
^записать_символ
сдвиг!
^преобразовать
^правило
интерпретация
состояние символ#
^Код0
A
B
C
...
Z
a
b
c
...
z
цифра
0 1 2 3 4 5 6 7 8 9
буква
та_пятерка?
пятерка
^правило
^Код0
0 1
состояниесдвиг# символ
RBсостояниеRB! символ
^RB
Код0
состояние
сдвиг
символ
состояние
символ
Код0
заменить
^зап_сдвиг
Код0!
^чтение?
символ#
пятерка
^Код0
^Код0
символ
сдвиг!
символ?
символ! символ?
символ
символ!
^если_0?
0
символ!
^если_0?
0
символ!
Рисунок. Граф метаописания интерпретатора U-машины в метаязыке НФЗ
Формальні методи розробки програмного забезпечення
45
Представленное определение ин-
терпретатора U-машины может быть при-
менено для решения задачи моделирова-
ния поведения любой Т-машины (решаю-
щей задачу преобразования данных на ее
ленте памяти), которая формулируется
обычным образом – как доказательство
общего суждения: "Любое значение дан-
ных из INP (начало которых определено
значением переменной m) суть интерпре-
тация".Вывод этого суждения идет в сле-
дующей последовательности. При анализе
со следом с понятиями "состояние" и
"символ" связываются: начальное состоя-
ние T-машины и первый символ на ее
ленте. Затем в итерационном цикле ин-
терпретируется последовательность поня-
тий "^поиск_правила" и "^преобразовать",
первое из них определяет ассоциативный
поиск пятерки, описывающей очередную
смену состояния моделируемой T-
машины, второе – замену на ленте T-
машины ранее взятого символа новым (из
соответствующей пятерки), читает оче-
редной символ (согласно указателю о
сдвиге головки T-машины) и записывает
на его место маркер T-машины. Поиск
подходящего правила T-машины выпол-
няется просмотром пятерок описания T-
машины отождествлением текущего и
связанного значений. Если проанализиро-
ванные со следом состояние или символ
не совпадают со значениями элементов
очередной пятерки, то пятерка пропуска-
ется, иначе – анализируются со следом
новое состояние, заменяющий символ
и значение сдвига головки T-машины.
Если все описание T-машины уже про-
смотрено безуспешно и на очереди разде-
ляющий Код0, то формируется значение
истинности "ложь", рекурсивный и затем
итерационный цикл прерываются и ин-
терпретатор заканчивает свою работу с
заключительным значением истинности
"истина". Иначе поиск пятерки рекурсив-
но повторяется до нужной пятерки или
пока не выявится, что запомненное состо-
яние – заключительное. Если пятерка
найдена, – после последовательной ин-
терпретации четного числа отрицаний го-
ловка U-машины возвращается к началу
описания T-машины. Интерпретация по-
нятия "^преобразовать" начинается с про-
пуска описания T-машины, затем пропуск
разделяющего символа и далее поиск
маркера. После того, как положение го-
ловки T-машины найдено, вместо маркера
записывается значение сдвига, затем ана-
лиз значения сдвига, запись на его место
заменяющего символа, чтение очередного
символа (слева или справа от маркера) и
запись вместо него маркера.
Рассмотренная интерпретация пред-
ставленного в метаязыке НФЗ определения
U-машины подтверждает его семантиче-
скую эквивалентность диаграмме состоя-
ний, составленной М. Минским [18].
Эта задача – пример задачи пове-
дения с фиксированной стратегией. Ее
смысл состоит в преобразовании данных
(представленных на ленте любой T-
машины) согласно знаниям (системе про-
дукций в форме диаграммы состояний
конкретной T-машины) о преобразова-
нии. Результат (в форме данных на ленте
T-машины) можно использовать как ко-
нечный результат или как исходные дан-
ные для следующей задачи. Работу U-
машины можно возобновить после уста-
новки головок в начальное положение и
смены данных и/или программы T-
машины.
Утверждение 13. Метаязык НФЗ
включает семантические возможности U-
машины, следовательно, любой 0-язык в
форме интерпретатора может быть опре-
делен в метаязыке НФЗ.
Используя этот результат, интер-
претирующе-транслирующий процесс по-
становки и решения произвольной задачи
представляется следующей последова-
тельностью преобразований:
на метаязыке описать интер-
претатор объектного языка и ввести в ма-
шину в качестве данных – разместить в
массиве INP;
выполнить ввод (трансляцию в
машинное представление) определения
интерпретатора объектного языка;
на объектном языке описать за-
дачу и ввести в машину в качестве данных
– разместить в массиве INP;
Формальні методи розробки програмного забезпечення
46
дать задание машине вывести
общее суждение в форме "Любое значение
данных из INP (чье начало определено
значением переменной m) суть интерпре-
тация объектного языка".
Результат: значение истинности
последнего суждения и преобразованные
данные.
9. Формализация в метаязыке
НФЗ транслятора Т-языка
Любая детерминированная T-
машина описывается [7] конечным множе-
ством продукций: iq ia jq ja id , фор-
ма которых совместно с определением
множеств Q ( iq , jq Q), ( ia , ja ) и
D ( id D) задает язык Т-машин (Т-язык).
Имя каждого состояния ( iq , jq )
из конечного множества Q пусть принад-
лежит объему понятия "имя_понятия",
алфавит пусть составлен как объедине-
ние объемов понятий "буква", "цифра" и
"знак" (их определение дано в [4]), и D –
пусть две выделенных константы ('0', '1'),
имеющих смысл сдвига читающе-
записывающей головки вправо и влево
соответственно.
Синтаксис этого языка формально
определим таким образом:
1) Т-язык = продукция (продук-
ция);
2) продукция = состояние1 пробел
символ1 фон '' фон состояние2 пробел
символ2 пробел сдвиг;
3) сдвиг = '0' / '1';
4) состояние1 = имя_понятия;
5) состояние2 = имя_понятия;
6) символ1 = буква / цифра /
^мета_знак знак ;
7) символ2 = буква / цифра /
^мета_знак знак.
Семантика любой продукции со-
стоит в смене одного состояния Т-машины
на другое, если текущий символ совпадает
с символом посылки; в случае применимо-
сти продукции – замена текущего символа
символом заключения и сдвиг читающе-
записывающей головки.
Семантику Т-языка формально
определим таким образом:
1) семантика_Т-языка =
Т_определения анализ_символов за-
пись_символов;
2) Т_определения =
Т_определение (Т_определение);
3) Т_определение = состояние1
Т_определяющее ';' ;
4) Т_определяющее = ' = '
Т_элемент ('/' Т_элемент / '/' 'истина');
5) Т_элемент = '^если_' символ1
пробел заключение;
6) заключение = '^записать_' сим-
вол2 пробел определение_сдвига пробел
состояние2 ';' пробел;
7) определение_сдвига = символ2
/ 'Сдвиг_влево' ;
8) анализ_символов = ана-
лиз_символа (анализ_символа);
9) запись_символов = запи-
сать_символ (записать_символ);
10) анализ_символа = '^если_' сим-
вол1 ' =df ' символ1 ';' пробел;
11) записать_символ = '^записать_'
символ2 ' = ' символ2 '!' ';' пробел.
Согласно этому определению се-
мантика любой конкретной Т-машины за-
дается конечным (не пустым) множеством
определений семантики всех ее состояний.
Любое состояние Т-машины – это альтер-
натива допустимых вариантов замены те-
кущего символа, сдвига читающе-
записывающей головки (вправо, пропуская
текущий символ, или влево, выполнив
терминал "Сдвиг_влево") и перехода в од-
но из следующих состояний (не обязатель-
но другое) в зависимости от значения те-
кущего символа. Здесь "Сдвиг_влево" –
всегда истинный терминал, определенный
в форме семантической процедуры, вы-
полняющей декремент значения m . На
множестве состояний любой конкретной
Т-машины считается известным (для ис-
пользования) ее начальное состояние iq ,
заключительное – определяется как
Формальні методи розробки програмного забезпечення
47
успешное завершение работы Т-машины,
которое достигается из произвольного
состояния в результате выяснения непри-
менимости преобразований текущего
символа, предусмотренных определением
состояния. Анализ и запись значений
символов (исходно указанных в продук-
циях Т-языка) представлены как отдель-
ные понятия, объединенные в соответ-
ствующие группы, расположенные (в
синтаксическом представлении в мета-
языке) после определений состояний Т-
машины.
Семантику трансляции определения
любой Т-машины из Т-языка в метаязык
формально определим следующим обра-
зом:
1) Т-язык_в_метаязык =
^преобр_прод RIO ^определ_вперед
^анализы_вперед ^нормализация RIO;
2) ^преобр_прод = преобр_1
(преобр_1);
3) преобр_1 = состояние1 пробел
символ1 фон '' фон состояние2 пробел
символ2 пробел# посылка '^записать_'
символ2 пробел! преобр_сдвиг? пробел
состояние2 ';' пробел анализ_символа за-
писать_символ!;
4) посылка = состояние1 '=df '
'^если_' символ1 '?' пробел;
5) преобр_сдвиг = '0'? символ2! /
'1'? 'Сдвиг_влево'!;
6) ^определ_вперед =
Т_определение (^вперед_определение
Т_определение);
7) ^вперед_определение = ана-
лиз_запись Т_определение# RIO
Т_определение анализ_запись! RIO;
8) анализ_запись = (ана-
лиз_символа / записать_символ);
9) ^анализы_вперед =
Т_определения (анализ_символов
^вначале_анализ);
10) ^вначале_анализ = запи-
сать_символ анализ_символа# RIO ана-
лиз_символа записать_символ! RIO;
11) ^нормализация = (скле-
ить_определения) (уда-
лить_дубли_анализа) (уда-
лить_дубли_записи);
12) склеить_определения = со-
стояние1 Т_определяющее# состояние1
Т_определяющее! ';' (^поиск_состояния? '/'
Т_элемент!)? '/' 'истина' ';'!;
13) ^поиск_состояния =
^взять_определение? RIO хвост RIO!
/Т_определение ^поиск_состояния;
14) ^взять_определение =
то_же_состояние? '=df ' Т_элемент ';'
хвост#;
15) то_же_состояние = RB со-
стояние1 RB! / ^RB;
16) хвост = (Т_определение)
(анализ_символа) (записать_символ) Код0;
17) удалить_дубли_анализа =
анализ_символа# анализ_символа!
(^тожд_анализ);
18) ^тожд_анализ =
^исключить_анализ? RIO хвост RIO! / ана-
лиз_символа ^тожд_анализ;
19) ^исключить_анализ =
тот_же_анализ? хвост#;
20) тот_же_анализ = RB ана-
лиз_символа RB! / ^RB;
21) удалить_дубли_записи = за-
писать_символ# записать_символ!
(^тожд_запись);
22) ^тожд_запись =
^исключить_запись? RIO хвост RIO! / за-
писать_символ ^тожд_запись;
23) ^исключить_запись =
та_же_запись? хвост#;
24) та_же_запись = RB запи-
сать_символ RB! / ^RB.
Это определение, как и любое дру-
гое, становится выполнимым (интерпрети-
руемым) после его ввода (трансляции в
машинное представление).
Результат его интерпретации:
представление в метаязыке НФЗ семанти-
ки любой Т-машины размещается с начала
массива INP, замещая исходное представ-
ление в Т-языке. Логический результат:
значение истинности – "истина", значения
переменных m и n – исходные.
Формальні методи розробки програмного забезпечення
48
Согласно данному определению
трансляция определения любой Т-машины
из Т-языка в метаязык НФЗ состоит в
следующей последовательности преобра-
зований.
При интерпретации понятия
"^преобр_прод" любая последовательность
продукций преобразуется из исходного
представления (в Т-языке) в представление
в метаязыке, причем каждая продукция
преобразуется независимо от других и
каждой из них ставится в соответствие три
определения взаимосвязанных понятий –
состояния (посылки), анализа (символа
посылки) и записи (символа заключения).
Результат преобразования – в массиве
OUT. По общему правилу интерпретации
инверсии: логический результат – "исти-
на", значения m и n – исходные.
Недостаток полученного представ-
ления (тот же, что и исходного) – при
его интерпретации необходим ассоциа-
тивный поиск нужного определения теку-
щего состояния из-за возможного наличия
в описании Т-машины нескольких, рас-
положенных в произвольном порядке,
независимых разных определений всякого
состояния. Последующие преобразования
направлены на устранение этого недостат-
ка и составляют упорядочение и нормали-
зацию определения любой Т-машины.
При интерпретации понятий
"^определения_вперед" и "^анализы_впе-
ред" выполняется упорядочение в массиве
OUT преобразованного определения Т-
машины: определения всех состояний пе-
ремещаются в начало, анализы символов
размещаются вслед за определениями со-
стояний, а записи символов остаются в
конце определения Т-машины.
В процессе интерпретации итера-
ции понятия "склеить_определения" вы-
полняется объединение множества раз-
личных определений любого состояния в
одно – определение состояния в форме
альтернативы допустимых в данном со-
стоянии преобразований текущего символа
и переходов в следующее состояние. В
процессе интерпретации итерации понятия
"удалить_дубли_анализа" исключаются
тождественные анализы символов, а ите-
рации понятия "удалить_дубли_записи" –
тождественные записи символов. Резуль-
тат этих преобразований порождается в
массив INP, замещая исходное представ-
ление в Т-языке.
Полученное определение (в мета-
языке) любой конкретной Т-машины по-
сле ввода и присоединения к имеющейся
базе знаний может быть применено для
решения соответствующей задачи обра-
ботки данных (введенных в массив INP),
которая формулируется обычным обра-
зом: как доказательство общего категори-
ческого суждения формы "Любое кон-
кретное значение данных из INP (начало
которых определено значением перемен-
ной m ) суть iq ", где iq – имя начального
состояния Т-машины, определение кото-
рой введено в базу знаний.
Представленная формализация
транслятора Т-языка обосновывает
Утверждение 14. Любой 0-язык в
форме транслятора может быть определен
в метаязыке НФЗ.
Используя этот результат, транс-
лирующе-транслирующий процесс по-
становки и решения произвольной задачи
некоторой предметной области определим
следующей последовательностью преобра-
зований [10]:
на метаязыке НФЗ описать
транслятор языка предметной области и
ввести в машину в качестве данных – раз-
местить в массиве INP;
выполнить ввод (трансляцию в
машинное представление) определения
транслятора языка предметной области и
присоединить к имеющейся базе знаний;
на языке предметной области
описать задачу и ввести в машину в каче-
стве данных – разместить в массиве INP;
дать задание машине вывести
общее суждение в форме "Любое значение
данных из INP (начало которых определе-
но значением переменной m ) суть транс-
лятор языка предметной области", резуль-
тат – значение истинности суждения и
определение на метаязыке НФЗ конкрет-
ной задачи предметной области;
выполнить ввод (трансляцию в
машинное представление) определения
Формальні методи розробки програмного забезпечення
49
(результат предыдущего пункта) этой кон-
кретной задачи и присоединить к имею-
щейся базе знаний;
исходные данные задачи разме-
стить в массиве INP;
дать задание машине вывести
общее суждение в форме "Любое значение
данных из INP (начало которых определе-
но значением переменной m ) суть начало
программы конкретной задачи".
Результат: значение истинности
последнего суждения и преобразованные
данные, смысл которых определяется се-
мантикой задачи.
Выводы
Исследованы выразительные воз-
можности метаязыка НФЗ по отношению к
формальным языкам разного уровня. По-
казано, что для формального языка каждо-
го уровня в метаязыке НФЗ есть адекват-
ные выразительные средства. Представ-
ленные результаты исследования, иллю-
стрированные множеством примеров,
обосновывают вывод об универсальных
выразительных возможностях метаязыка
НФЗ, о его пригодности в качестве базово-
го инструмента для реализации языков и
систем произвольной сложности и назна-
чения.
1. International Standard ISO/IEC 14977 :
1996(E). Электронный ресурс. Режим до-
ступа: http://www.cl.cam.ac.uk/~mgk25/iso-
14977.pdf
2. Спосіб представлення і використання
знань / О.П. Кургаєв, С.М. Григор’єв / Па-
тент на корисну модель UA 92484 U,
2014р., Бюл. №16.
3. Kurgaev A., Grygoryev S. The normal forms
of knowledge. Dopov. NAN Ukraine, 2015,
№ 11. Р. 36–43.
4. Кургаев А.Ф., Григорьев С.Н. Метаязык
нормальных форм знаний. Кибернетика и
системный анализ. 2016. Том. 52. № 6.
С. 11–20.
5. Ершов А.П. Предварительные соображе-
ния о лексиконе программирования. Ки-
бернетика и вычислительная техника. Под
ред. В.А. Мельникова. 1985. Вып. 1.
С. 199–210.
6. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Алгебра. Языки. Программирование. К.:
Наук. думка, 1978. 320 с.
7. Гросс М., Лантен А. Теория формальных
грамматик. М.: Мир, 1971. 294 с.
8. Хомский Н. Формальные свойства грамма-
тик. Кибернетический сборник. Новая се-
рия. М.: Мир, 1966. Вып. 2. С. 122–230.
9. Войшвилло Е.К. Понятие как форма мыш-
ления: логико-гносеологический анализ.
М.: Изд. МГУ, 1989. 239 с.
10. Кургаев А.Ф. Проблемная ориентация ар-
хитектуры компьютерных систем. Киев:
Сталь, 2008. 540 с.
11. Тейз А., Грибомон П., Луи Ж. и др. Логи-
ческий подход к искусственному интел-
лекту: от классической логики к логиче-
скому программированию. Пер. с фр.; Под
ред. Г.П. Гаврилова. М.: Мир, 1990. 432 с.
12. Хомский Н. и Миллер Дж. Введение в
формальный анализ естественных языков.
Кибернетический сборник. Новая серия.
М.: Мир, 1965. Вып. 1. С. 229–290.
13. Хомский Н. О некоторых формальных
свойствах грамматик. Кибернетический
сборник. М.: Изд-во иностр. лит., 1962.
Вып. 5. С. 279–311.
14. Гильберт Д., Бернайс П. Основания мате-
матики: Теория доказательств. М.: Наука,
1982. 652 с.
15. Кургаев А.Ф. Логические формы опреде-
ления понятия. УСиМ. 1998. № 2. С. 3–12.
16. Chomsky, N.: Aspects of the Theory of
Syntax, MIT Press, Cambridge, MA, 1965.
17. Fu K.S. Syntactic Pattern Recognition and
Applications. New Jersey: Prentice-Hall, Inc.,
Englewood Cliffs, 1982. 596 p.
18. Minsky M.L. Computation: Finite and Infinite
Machines. NY: Prentice-Hall, Englewood
Cliffs, 1967.
19. Kurgaev A., Grygoryev S. The Universal
Turing Machine Interpreter. Dopov. NAN
Ukraine, 2016, 10. С. 28–34.
https://doi.org/10.15407/dopovidi2016.10.028
20. Shannon C.E. A universal Turing machine
with two internal states. Princeton: Automata
Studies, 1956.
References
1. International Standard ISO/IEC 14977 :
1996(E). [Electronic resourse]. – Mode of
http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
Формальні методи розробки програмного забезпечення
50
access: http://www.cl.cam.ac.uk/~mgk25/iso-
14977.pdf
2. Kurgaev A., Grygoryev S. Utility model
patent UA 92484 U, 2014, Bulletin № 16 (in
Ukrainian).
3. Kurgaev, A. The normal forms of knowledge /
A.Kurgaev, S.Grygoryev. – Dopov. NAN
Ukraine, 2015, № 11. – Р. 36-43 (in Russian).
4. Kurgaev, A. Metalanguage of Normal Forms
of Knowledge / A.Kurgaev, S.Grygoryev. –
Cybernetics and Systems Analysis. –
November 2016, 52(6). – P. 11-20. (in
Russian).
5. Ershov, A.P. Preliminary considerations on
the lexicon of programming // Cybernetics
and computer technology / Ed. V.A.
Melnikov. - 1985. - Vyp. 1. – P. 199–210. (in
Russian).
6. Glushkov, V. Algebra. Languages.
Programming / V.Glushkov, G.Zeitlin,
E.Yushchenko. – K.: Nauk. Dumka, 1978. –
320 p. (in Russian).
7. Gross M. Theory of formal grammars /
M.Gross, A.Lunten. – M.: Mir, 1971. - 294 p.
(in Russian).
8. Chomsky, N. Formal properties of grammars.
/ Cybernetic collection. New episode. –
Moscow: Mir, 1966. – Vyp. 2. – P. 122–230.
(in Russian).
9. Voishvillo E. Concept as a form of thinking:
logical-gnoseological analysis / E. Voishvillo.
– Moscow: Izd. MSU, 1989. – 239 p. (in
Russian).
10. Kurgaev, A.F. Problem orientation of the
architecture of computer systems / A.F.
Kurgayev. – Kiev: Steel, 2008. – 540 p. (in
Russian).
11. Teiz, A. Logical approach to artificial
intelligence: from classical logic to logical
programming / A. Teiz, P. Gribomon, J. Louis
et al. – Transl. With fr .; Ed. G.P. Gavrilov. –
Moscow: Mir, 1990. – 432 p. (in Russian).
12. Chomsky, N. Introduction to the formal
analysis of natural languages / N. Chomsky, J.
Miller. – Cybernetic collection. New episode.
– Moscow: Mir, 1965. – Vyp. 1. – P. 229–
290. (in Russian).
13. Chomsky, N. On some formal properties of
grammars / Cybernetic collection. – Moscow:
Izd-vo inostr. Lit., 1962. - Vyp. 5. – P. 279–
311. (in Russian).
14. Gilbert, D. Foundations of Mathematics:
Theory of Evidence / D.Gilbert, P.Bernays. –
M oscow: Nauka, 1982. – 652 p. (in Russian).
15. Kurgaev A. Logical forms of definition of the
concept // Control Systems and Computers. –
1998. – № 2. – P. 3–12. (in Russian).
16. Chomsky, N. Aspects of the Theory of
Syntax, MIT Press, Cambridge, MA, 1965.
17. Fu, K.S. Syntactic Pattern Recognition and
Applications. – New Jersey: Prentice-Hall,
Inc., Englewood Cliffs, 1982. – 596 p.
18. Minsky, M.L. Computation: Finite and
Infinite Machines. – NY: Prentice-Hall,
Englewood Cliffs, 1967.
19. Kurgaev, A. The Universal Turing Machine
Interpreter / A.Kurgaev, S.Grygoryev. –
Dopov. NAN Ukraine, 2016, 10. – P. 28-34.
https://doi.org/10.15407/dopovidi2016.10.028
(in Russian)
20. Shannon, C.E. A universal Turing machine
with two internal states. – Princeton:
Automata Studies, 1956.
Получено 23.05.2017
Об авторах:
Кургаев Александр Филиппович,
доктор технических наук,
профессор, ведущий научный сотрудник.
Количество публикаций в
украинских изданиях – более 200.
Количество публикаций в
зарубежных индексированных
изданиях – около 10,
H-індекс (Google Scholar): 4
http://orcid.org/0000-0001-5348-2734,
Григорьев Сергей Николаевич,
соискатель.
Количество публикаций в
украинских изданиях – более 20.
http://orcid.org/0000-0002-7583-3088.
Место работы авторов:
Институт кибернетики
имени В.М. Глушкова НАН Украины.
03187, Киев-187,
проспект Академика Глушкова, 40.
Тел.: 050 881 6218,
050 505 05 75.
E-mail: afkurgaev@ukr.net,
Sergey@Grigoriev.kiev.ua
http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
https://doi.org/10.15407/dopovidi2016.10.028
mailto:afkurgaev@ukr.net
mailto:Sergey@Grigoriev.kiev.ua
|