Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
— грамматики, см. Емкость грамматики 57
— отношения эквивалентности 17 Инструкция 42
Интервал цепочки 21
----несобственный 21
----подстрелочный 299
----- — правильный 299
Итерация языка 23 ---- усеченная 23
— Э-машины 164
Конкатенация языков, см. Умножение языков, Произведение языков 22 Контекст в НС-правиле 29 --------левый 29
— — — правый 29 Конфигурация 319—320
— простая 321 Корень (дерева) 18 Коэффициент 24
КС-грамматика, см. Грамматика бесконтекстная 29 КС-правило, см. Правило бесконтекстное 29 Куст узла 18
Левее (а лежит левее |5; а расположена левее р) 21 Лемма о замещении 96 ------ сцеплении 64
— ----- сильном 95
Лента входная 41
— конечного автомата 160
— рабочая 41
ЛЗ-сегмент, см. Сегмент лексически значимый 315 Лингвистика математическая 13
Категория 185
— главная 186
— элементарная 185—186 К-грамматика, см. Грамматика
категориальная 186 Класс, порожденный окрестностью 328 —, — семейством 328
— приведенный 337 Код грамматики 73
— цепочки 73
— Э-машины 258 Композиция Э-машин параллельная 164
---- последовательная 164
Конгруэнция 316 Конец дуги (в графе) 18 ----(в мультиграфе) 19
— пути 18
— цепочки 20 Конкатенация цепочек 20
Мажорирование (функция g(h) мажорируется функцией h (я)) 59
Маркер граничный в Э-машине левый 42
----------- правый 42
Машина с магазинной памятью ( = МП-машина) 137
•----— — нормальная 138
--------— однодорожечная 168
— — — — однозначная 150
— — — — равномерная 169
— --------с выходом 154
— —-------с ограниченным чис-
лом поворотов 171
-------------- I поворотами 171
— — — — счетчиковая 155 — чисто стирающая
170
— Тьюринга с неэластичной рабочей лентой ( = Н-мацшна)
Предметный указатель
361
Машина Тьюринга с неэластичной рабочей лентой детерминированная (= ДН-машина) 53
— — ------------ одноленточная
(=ОН-машина) 53
--------------------детерминированная ( = ДОН-машина) 53
—----эластичной рабочей
лентой ( = Э-машина) 41
-----------------без растяжения 85
— — — — — — детерминированная ( = ДЭ-машина) 44
— — — — — — несамоприме-нимая 259
-----------------с ограниченным
растяжением 87
— — — — — — самопримени-t. мая 259
-----------------числовая 53
Между (Р лежит между а и у)
21
Меньше по порядку 97 Метаязык 11
Метка в дереве подчинения 298
---системе составляющих 291
Многочлен 24
— замкнутый 24
Множество векторов линейное
129
--- полулинейное 130
— натуральных чисел периодическое 181
— нумерационно рекурсивно перечислимое ( = н. р. п. м.) 53
— опорное (формального ряда) 211
— рекурсивно перечислимое 49 числовое (=ч. р. п. м.)
53
Модель одноленточная прямая ( = п. о. м.) 45
— парадигматическая 324
— синтагматическая 324 МП-машина, см. Машина с магазинной памятью 137
Мультиграф 19
Находиться (головка находится в ячейке), см. Обозревать 42 Начало'дуги (в графе) 18
— — (в мультиграфе) 19
Начало пути 18
— цепочки 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
