Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Подчинение (узел А подчиняет узел В) 18 Полугнездо левое 289 .
— правое 289
Полугруппа 315 •— свободная 316 Получаться (цепочка т] получается из са применением правила г) 28 П. о. м., см. Модель одноленточная прямая 45 Порядок стандартный 22 Построить 32
Потомок интервала в цепочке • 94
— —--------точный 94
— узла 80
------непосредственный 79
Почти совпадать (языки почти совпадают) 264 Правее (|3 лежит правее а, Р расположена правее а) 21 Правило (грамматики) 27
— бесконтекстное (-Б-правило)
29
— заключительное 30
— контекстно-свободное, см. Правило бесконтекстное 29
— неукорачивающее 84 Правильность грамматическая 16 Предел последовательности множеств 211
?--------верхний 211
---------нижний 211
Предикат нераспознаваемый 254
— распознаваемый 254 Предок интервала в цепочке 94
—--------точный 94
— узла 80
Представление каноническое 213
Представляться (язык представляется многочленом) 24 Применение правила 28 Приписывать (грамматика приписывает цепочке категорию) 186
Проблема алгоритмическая 252
------неразрешимая 252
------разрешимая 252
— массовая 252 Программа 42
Прогрессия арифметическая 34 Проектирование 23 Проекция цепочки 24 р- языка 24
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
363
Произведение прямое, см. Произведение языков 22
— цепочек, см. Конкатенация цепочек 20
— языков 22
Производить (путь производит цепочку) 159 Происходить левее (о шаге вывода) 31
— правее (о шаге вывода) 31 Протокол 269
Путь (в графе) 18
— (в мультиграфе) 19
— без ветвления 219
— замкнутый 18
— левый 196
— полный (в диаграмме) 159
— правый 196
— старший 237 Пучок языков 265
Равенство многочленов тождественное, см. Тождественность многочленов 25 Равносильность выводов 31 Разброс 57 Раздел 341
Разделять (пары точек разделяют друг друга) 21 Ранг составляющей 287
— узла (в дереве) 18 Распознавание языка ДЭ-маши-ной 45
Pi-дерево, см. Дерево расположенное с помеченными узлами 81
Рг-дерево, см. Дерево расположенное с помеченными узлами и дугами 82 Результирующий 319—320 Решение нормальной системы уравнений 208
-----------наименьшее 209
Ряд степенной формальный некоммутативный 211
Сводимость алгоритмических проблем 256 Свойство булево 261
— инвариантнре ?54
Свойство нераспознаваемое 254
— нетривиальное 255
— распознаваемое 254 Связанность (иерархизованной
системы составляющих и дерева подчинения) 305 Сегмент 16
— лексически значимый ( = ЛЗ-сегмент) 315
Семейство 327 Сечение (цепочки) 96 Сигнализирующая грамматики, см. Функция сигнализирующая грамматики 56
— — относительно класса грамматик, см. Функция сигнализирующая грамматики относительно класса грамматик 57
— Э-машины, см. Функция сигнализирующая Э-машины 63
Символ, см. Символ элементарный 19
— бесплодный 122
— вспомогательный 27
-----неустранимый 123
-----устранимый 123
----- циклический 123
— начальный 27
— нетерминальный, см. Символ вспомогательный 27
— основной в категориальной грамматике 186
--------порождающей грамматике 27
— самовставляющийся 244
— терминальный, см. Символ основной 27
— элементарный 19
— Z-бесплодный 122 Система категориальная 185
— образующих полугруппы 315
— составляющих 282
----- бинарная 287
----- иерархизованная 291
-----размеченная 291
— уравнений нормальная 208 Ситуация 43
— заключительная 43
— начальная 43
— правильная 268 След вывода 96 Словарь 19
364
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Словарь вспомогательный 27
— категорий 185—186
— нетерминальный, см. Словарь вспомогательный 27
— основной категориальной грамматики 186
-------порождающей грамматики
27
— полный (грамматики) 27
— терминальный, см. Словарь основной 27
Слово (в лингвистическом смысле) 16
— (в математическом смысле), см. Цепочка 19
Словосочетание 283
Словоформа 16
Сложение формальных рядов 220
Сложность временная 57
— категориальной грамматики 195
— категории 195
Совместимость отношения эквивалентности с конкатенацией справа 181
Согласованность отношения эквивалентности с языком 318
— системы составляющих и дерева подчинения 304
Сокращение (| сокращается до
г)) 186
— непосредственное (1 непосредственно сокращается до г})
186
Соответствие (между грамматиками) каноническое 189
Сопоставление дерева подчинения цепочке Д-грамматикой 201
— цепочки категорий цепочке в основном словаре 186
Составляющая 282
— главная 291
— левая 289
— неуглубляющая 289
— полная 282
— правая 289
— средняя 289
— точечная 282
— тривиальная 282
— углубляющая 289
Состояние внутреннее 42
Состояние заключительное 42
— начальное 42 Степень Б-грамматики 205
— гнездования грамматики 242
---системы составляющих 289
---составляющей 288
— дерева 19
— левого ветвления системы составляющих 289
—------составляющей 288
— правого ветвления системы: составляющих 289
—------составляющей 288
— самовставления грамматики: 242
— символа 205
— системы составляющих 287
— составляющей 287
— узла (в дереве) 18 Схема грамматики 27
— склонения 338
— согласования 338
— управления 336
Тезис Черча 49 Теорема Клини 165
— о нормальной форме 196
