Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Выражение подстановочное
238
— регулярное 24 замкнутое 24
— центрально-подстановочное 177
Высота грозди 229
— Д-грамматики 207
— дерева 19
— системы составляющих 287
— составляющей 287
— узла (в дереве) 18 Вычисление (Э-машины) 43 Вычисляет (машина М вычисляет функцию [) 47
Вычитание (теоретико-множественное) 22
358
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Глубина левая 57
— правая 57 Гнездо 288
— однородное 242
Головка конечного автомата 160
— Э-машины входная 42
---- рабочая 42
Гомоморфизм, см. Отображение
гомоморфное 23 —' алфавитный 317
— естественный 316 Грамматика,, см. Грамматика порождающая 27
— автоматная ( = А-граммати-ка) 29
----без омонимии 340
?--обобщенная (=ОА-грам-
матика) 157
-------- стандартная 158
---- й-опредеденная 180
— без растяжения 85
— бесконтекстная ( = Б-грамматика) 29
?--без самовставления 244
— — в нормальной форме, см.
Грамматика бесконтекстная в нормальной форме Грейбах 197
--------------- Грейбах 197
— — обобщенная ( = ОБ-грам-матика) 125
-------- итерационно-линейная
174
?------линейная 168
?---------левосторонняя 169
—------правосторонняя 169
?---------симметричная 169
— — — металинейная 170
— — ограниченной активной емкости (Б-ОАЕ-грамматика) 234
— — однозначная 126
---- приведенная 123
---- слабо бинарная 235
---- стандартная бинарная 116
----удлиняющая 200
— доминационная ( = Д-грамматика) 200
----без циклов 202
— — ограниченной высоты 207 ширины 203
— — однозначная 219
Грамматика доминационная про- ‘ стая 202
— зависимостей, см. Грамматика доминационная простая
202
— категориальная ( = К.-грамма-тика) 186
-----категориально однозначная 218 ;
— — левосторонняя 195 .*
----- правосторонняя 195 ;
----- синтаксически однозначная ‘
218 1 V
— конечно-автоматная, см. Грам- 1
матика автоматная 30 ?.[.
— контекстно-неукорачивающая 250
— контекстно-свободная, см. • Грамматика бесконтекстная 29
— непосредственно (непосредственных) составляющих, см. Грамматика составляющих 29
— неукорачивающая 84
— окрестностная простая 179
— порождающая 27
— почти неукорачивающая 88
— с конечным числом состояний, см. Грамматика автоматная 29
-----ограниченной активной емкостью выводов (=ОАЕВ-грамматика) 174 -----ограниченным растяжением 87
— самопорождающая 279
— сильно сцепленная 95
— составляющих ( = НС-грамматика) 29
----- левоконтекстная 105
-----обобщенная (=ОНС-грам-
матика) 113
----- однозначная 83
----- правоконтекстная 105
----- с односторонним контекстом, см. Грамматика составляющих левоконтекстная, Грамматика составляющих правоконтекстная 105
— со стоп-правилами 51
— сцепленная 64
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
359
Грамматика универсальная 112
— формальная 10, 25 Граф 17
Гроздь (цепочки) 229 Группа зависимости 18
---усеченная 294
Густота дерева 237
— узла 237
Д-автомат, см. Автомат древообходящий 140 Д-грамматика, см. Грамматика доминационная 200 Деление цепочек левое 20
— — правое 20
— языка на цепочку левое 23
?-- -----правое 23
Дерево 18
— бинарное 18
•— вывода в грамматике составляющих 81
— — — обобщенной бесконтекстной грамматике 126
--- растянутое 79
---сжатое 82
— вычисления 139 упрощенное 140
— единичное 19
— подчинения, см. Дерево синтаксического подчинения 294
— расположенное с помеченными узлами ( = Ргдерево) 81
--------------линейное 168
--------------и дугами ( =Р2-
дерево) 82
--------------------- линейное
168
— синтаксического подчинения 294
--- — проективное 299
------- размеченное 298
—• — — слабо проективное 299
— сокращения 189
— составляющих 287 Диаграмма конечного автомата
160
— линейной обобщенной бесконтекстной грамматики 182
— обобщенной автоматной
грамматики 158
ДК-автомат, см. Автомат конечный двулентрчный 182
Длина вывода 28
— вычисления (Э-машины) 43
— пути 18
— цепочки 19
ДН-машина, см. Машина Тьюринга с неэластичной рабочей лентой детерминированная 53
ДОН-машина, см. Машина Тьюринга с неэластичной рабочей лентой одноленточная детерминированная 53
Дополнение 22
Допускать1 (Э-машина допу-
скает цепочку) 44
Допускать2 (Д,К.-автомат допускает пару цепочек) 182
Достижимость (ситуация S' достижима из ситуации S - в Э-машине) 43
— непосредственная 43
Дуга (в графе) 18
— (в мультиграфе) 19
ДЭ-машина, см. Машина Тьюринга с эластичной рабочей лентой детерминированная 44
Единица (полугруппы) 315 Емкость вывода активная 174
— грамматики 57 активная 57
— цепочки активная 174
— Э-машины 63
Зависимость (в графе) 18
— символов (в бесконтекстной грамматике) 121 Задаваться, см. Представляться 24
Заменяться (вхождение заменяется на l-м шаге вывода)
28
Замещаемость 318 Замкнутость класса грамматик эффективная 32 Замыкание языка коммутативное
112
Запись правильной ситуации
268
360
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Запись простейшая (натурального числа) 34 Зацепленность (о шаге вывода)
31
— сильная 95
Значение грамматическое 16
— лексическое 16
Зона влияния (сечения) 96
Иерархизация 291
— допустимая 201
— обратная 190
— прямая 190
Изоморфизм (полугрупп) 316 Индекс ветвления (дерева вывода) приведенный 175
