Гладкий - Формальные грамматики и языки - 1973 (947381), страница 74
Текст из файла (страница 74)
р. п, м.) 53 — опорное (формального ряда) 211 — рекурсивно перечислимое 49 — — — числовое ( ч. р, п. и.) 53 Модель однолеиточная прямая (= п. о. м.) 45 — параднгматнческая 324 — синтагматическая 324 МП-машина, см. Машина с магазинной памятью Г37 Мультиграф 19 Находитьси (голазна находится з ячейке), см. Обозревать 42 Начало дуги (в графе) 18 — — (в мультиграфе) 19 Начало пути !8 — цепочки 20 Неизвестная 207 Н-машина, см. Машина Тьюринга с неэластичной рабочей .чеитой 52 Номер цепочки стандартный 22 Н. р, п, м., см.
Множество нумерационно рекурсивно перечислимое 53 НС-грамматика, см, Грамматика составляющих 29 НС-правило 29 НС-язык 30 Н.ч. р.ф., см. Функция нумерационно частична рекурсивная 53 ОА-грамматика, см. Грамматика, автоматная обобщенная 157 ОА-язык, см. Язык автоматный обобщенный 157 ОАЕ-язык, см. Язык ограниченной активной емкости 234 ОАЕВ-грамматика, см. Грамматика с ограниченной активной емкостью выводов 174 ОАЕВ-язык 174 ОБ-грамматика, см. Грамматика бесконтекстная обобщенная 125 Обозревать (голозка обозревает ячейку) 42 Образ гомоморфный ОБ-языка 126 Обращение цепочки 35 — языка 156 Объединение 22 ОБ-язык 125 Окрестность (в простейшей окрестностной А-грамматике с порядком) 142 Окрестность (в лексически размеченном языке) 328 Омонимия синтаксическая 285 ОН-машина, см. Машина Тьюринга с незластичной рабочей лентой одноленточная 53 ОНС-грамматика, см. Граммати.
ка составляющих обобщенная 113 362 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Оператор квазисигнализирующий для грамматик 56 — — — Э-машин 62 — НС-сигнализирующий 84 — снгналнзирующий для грамматик 56 — — — Э.машин 63 — — относительный 57 Операции над цепочками, см. Конкатенация цепочек, Деление цепочек левое, Деление цепочек правое 20 — — языками, см.
Объединение, Пересечение, Умножение языков, Итерация, Итерация усеченная, Деление языка на цепочку левое, Деление языка на цепочку правое, Подстановка, Проектирование, Отображение гомоморфное, Обращение 22 — 23, 156 Отношение бинарное 17 — инвариантное между грамматиками 254 — нераспознаваемое 254 — подчинения, см.
Отношение синтаксического подчинения 294 — распознаваемое 254 — синтаксического подчинения 294 — — — проективпое 299 — — — слабо проективное 299 Отображение гомоморфное 23, 316 — изоморфное 316 Отрезок цепочки 21 — циклический 300 Парадигма 334 Пересечение 22 Перестройка вывода 30 ПО-грамматика, см. А.грамматика окрестностнан простейшая с порядном 142 Поддерево полное 120 Подстановка 23 — центральная 177 Подцепочка 21 Подчинение (узел А подчинягг узел В) 18 Полугиездо левое 289 — правое 289 Полугруппа 315 — свободная 3!6 Получаться (цгпочни ц получается из ю примгнгнигмлравила г) 28 П.о.м., см. Модель одноленточная прямая 45 Порядок стандартный 22 Построить 32 Потомок интервала в цепочке . 94 — — — — точный 94 — узла 80 — — непосредственный 79 Почти совпадать (языки почти совпадают) 264 Правее ()) лежит правее а, расположена нравгг а) 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 Произведение прямое, см. Произведение языков 22 — цепочек, см.
Конкатенация цепочек 20 — языков 22 Производить (путь производит цепочку) 159 Происходить левее (о шаге вывода) 31 — правее (о шаге вывода) 31 Протокол 269 Путь (в графе) 18 — (в мультиграфе) 19 — без ветвления 219 — замкнутый 18 — левый 196 — полный (в диаграмме) 159 — правый 196 — старший 237 Пучок языков 265 Равенство многочленов тождественное, см, Тождественность многочленов 25 Равносильность выводов 31 Разброс 57 Раздел 341 Разделять (пиры точек разделяют друг друга) 21 Ранг составляющей 287 — узла (в дереве) 18 Распознавание языка ДЭ-машиной 45 Рмдерево, см.
Дерево расположенное с помеченными узла. ми 81 Рз-дерево, см. Дерево расположенное с помеченными узла. ми и дугами 82 Результирующий 3 !9 — 320 Решение нормальной системы уравнений 208 — — — — наименьшее 209 Ряд степенной формальный некоммутативный 21! Сводимость алгоритмичесних проблем 256 Свойство булево 261 — инвариантное 264 Свойство нераспознаваемое 254 — нетривиальное 255 — распознаваемое 254 Связанность (иерархизованной системы составляющих и дерева подчинения) 305 Сегмент 16 — лексически значимый (=ЛЗ- сегмент) 315 Семейство 327 Сечение (цепочки) 96 Сигналиэирующая грамматики, см.
Функция сигнализирующая грамматики 56 — — относительно класса грамматин, см. Фуннцвя сигнализирующая грамматики атно- сительно класса грамматик 57 — Э-машины, см. Функция сигнализируюшая Э-машины 63 Символ, см. Символ элементарный 19 — бесплодный 122 — вспомогательный 27 — — неустранимый 123 — — устраиимый 123 — — циклический 123 — начальный 27 — нетерминальный, см. Символ вспомогательный 27 — основной в категориальной грамматике 186 — — — порождающей грамматике 27 — самовставляющийся 244 — терминальный, см.
Символ основной 27 — элементарный 19 — 3-бесплодный 122 Система категориальная 185 — образующих полугруппы 315 — составляющих 282 — — бинарная 287 — — иерархизованная 291 — — размеченная 291 — уравнений нормальная 208 Ситуация 43 — заключительная 43 — начальная 43 — правильная 268 След вывода 96 Словарь 19 предметнып Указатель 365 ПВЕДМЕТНЫЯ УКАЗАТЕЛЬ 364 Словарь вспомогательный 27 — категорий !85 †1 — негерминальный, см.
Словарь вспомогательный 27 — основной категориальной грамматвки !86 — — порождающей грамматики 27 — полный (грамматики) 27 — терминальный, см. Словарь основной 27 Слово (в лингвистическом смысле) !6 — (в математичесиом смысле), см. Цепочка 19 Словосочетание 283 Словоформа 16 Сложение формальных рядов 220 Сложность временная 57 — категориальной грамматики 195 — категории 195 Совместимость отношения эквивалентности с конкатенацией справа 181 Согласованность отношения эквивалентности с языком 318 — системы составляющих и дерева подчинения 304 Сокращение ($ сокращается до т)) 186 — непосредственное (5 кепосредсгвенно сокращаетгл до Ч) 186 Соответствие (между грамматикамн) каноническое 189 Сопоставление дерева подчине.
иия цепочке Д.грамматикой 201 — цепочки категорий цепочке в основном словаре 186 Составляющая 282 — главная 29! — левая 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 Теорема Клиии !65 — о нормальной форме 196 — — сжатии выводов 67 — — — вычислений 70 — об ускорении выводов 69 — — — вычислений 70 — Райса 257 Тип 328 Тождественность многочленов 25 Точка главная (составляющей) 306 — цепочки 2! Узел Висйчий 18 — графа 18 — диаграммы конечного автома та заключительный 160 — — — — начальный 160 — — ОА-грамматики заключи' тельный 158 — — — начальный 158 — изолированный 18 — левый 191 — мультиграфа !9 — отмеченный 200 — правый 191 Укрупнение отношения эквивалентности 3!7 — — — Е-регулярное 325 Умножение прямое, см.
Умножение языков 22 — формальных рядов 220 — — — адамарово 220 — цепочек, см. Конкатенация цепочек 20 — языков 22 Фактор-биграф 80 фактор-множество 17 фактор-полугруппа 316 форма нормальная Грейбах, см. Грамматика бесконтекстная в нормальной форме Грейбах 197 Формула регулярная !65 Функция квазисигналнзирующая грамматики 56 — — Э-машины 62 — множеств неубывающая 208 — НС-сигнализирующая грамматики 84 — нумерационно частично рекурсивная (и. ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
