Гладкий - Формальные грамматики и языки - 1973 (947381), страница 73
Текст из файла (страница 73)
Равносильность выводов 3! Выражение подстановочное 238 — регулярное 24 — — замкнутое 24 — центраяьно-подстановочное |77 Высота грозди 229 — Д-грамматики 207 — дерева 19 — системы составляющих 287 — составляющей 287 — узла (в дереве) 18 Вычисление (Э-машины) 43 Вычисляет (машина М вычисляет Функцию [) 47 Вычитание (теоретико-множествеаное) 22 и Р едьте ты ы и укдзлтель предметныц указатель Глубина левая 57 — правая 57 Гнездо 288 — однородное 242 Головка конечного автомата 160 — Э-машины входная 42 — — рабочая 42 Гомоморфизм, см.
Отображение гомоморфное 23 — алфавитный 317 — естественный 316 Грамматика,, см. Грамматика по. рождающая 27 — автоматная (=А.грамматика) 29 — — без омонимии 340 — — обобщенная (=ОА-грамматика) 157 — — — стандартная 158 — — й-определенная !80 — без растяжения 85 — бесконтекстная ( =Б-грамма- тина) 29 — без самовставления 244 — — в нормальной форме, см. Грамматика бесконтекстная в нормальной форме Грейбах 197 — — — — — Грейбах !97 — — обобщенная (=ОБ-грамматика) 125 — — — нтерационно-линейная 174 — — линейная 168 — — — — левосторонняя 169 — — — — правостороиняя !69 — — — — симметричная 169 — — — металинейная 170 — ограниченной активной емкости (Б-ОАЕ-грамматнка) 234 — — однозначная 126 — — приведенная !23 — — слабо бинарная 235 — — стандартная бинарная 1!6 — — удлиняющая 200 — доминационная (=Д-грамма.
тика) 200 — — без циклов 202 — — ограниченной высоты 207 — — — ширины 203 — — однозначная 2!9 Грамматика домннационная про. стая 202 — зависимостей, см. Грамматнна домннационная простая 202 — категориальная (=К-грамматика) 186 — — категориально однозначная 2!8 — — левостороиняя !95 — — правосторонняя !95 — — синтаксически однозначная 218 — конечно-автоматная, см.
Грамматика автоматная 30 — коитекстно-неукорачиваюшая 250 — контекстно-свободная, см. Грамматика бесконтекстная 29 — непосредственно (непосредственных) составляющих, см. Грамматика составляющик 29 — неукорачивающая 84 — окрестностная простая 179 — порождающая 27 — почти неукорачивающая 88 — с конечным числом состояний, см.
Грамматика автоматная 29 — — ограниченной активной емкостью выводов (=ОАЕВ- грамматика) 174 — — ограниченным растяжением 87 — самопорождающая 279 — сильно сцепленная 95 — составляющих (=НС-грамматика) 29 — — левоконтекстная 105 — — обобшенная (=ОНС-грам. матика) !13 — — однозначная 83 — — правоконтекстная !05 — — с односторонним контек. стом, см. Грамматина составлявших левоконтекстная, Грамматика составляющих правоконтекстная 105 — со стон-правилами 51 — сцепленная 64 Грамматика универсальная 112 — формальная !О, 25 Граф 17 Гроздь (цепочки) 229 Группа зависимости 18 — — усеченная 294 Густота дерева 237 — узла 237 Д-автомат, см.
Автомат древо- обходящий !40 Д-грамматика, см. Грамматика доминационная 200 Деление цепочек левое 20 — — правое 20 — языка на цепочку левое 23 — — — — правое 23 Дерево 18 — бинарное 18 вывода в грамматике составляющих 8! — — — обобщенной бесконтекстной грамматике 126 — — растянутое 79 — — сжатое 82 — вычисления 139 — — упрощенное 140 — единичное 19 подчинения, см.
Дерево синтаксического подчинения 294 — расположенное с помеченными узлами (=Ргдерево) 81 — — — — — линейное 168 — — — — — и дугами ( =Р,- дерево) 82 — — — — — — — линейное 168 — синтаксического подчинения 294 — — — проектввное 299 — — — размеченное 298 — — — слабо проективное 299 — сокращения 189 — составляющих 287 Диаграмма конечного автомата 160 — линейной обобщенной бесконтекстной грамматики 182 — обобшенной автоматной грамматики 158 ДК-автомат, см. Автомат конечный двуленточный 182 Длина вывода 28 — вычисления (Э-машнны) 43 — пути 18 — цепочки 19 ДН-машина, см.
Машина Тьюринга с неэластичной рабочей лентой детерминированная 53 ДОН-машина, см. Машина Тьюринга с неэластичной рабочей лентой одноленточная детерминированная 53 Дополнение 22 Допускать ' (Э-лгашяиа допускает цепочку) 44 Допускать' (ДК-автомат допускает лару цепочек) 182 Достнжимост (ситуация 3' достижима из ситуации 3 . в Э-машинв) 43 — непосредственная 43 Дуга (в графе) 18 — (в мультиграфе) 19 ДЭ-машина, см, Машина Тьюринга с эластичной рабочей лентой детерминированная 44 Единица (полугруппы) 315 Емкость вывода активная 174 — грамматики 57 — — активная 57 — цепочки активная 174 — Э-машииы 63 Зависимость (в графе) !8 — символов (в бесконтекстной грамматике) !21 Задаваться, см.
Представляться 24 Заменяться (вхождение замвнявгся на 1-м шаге вывода) 28 Замещаемость 3!8 Замкнутость класса грамматик эффективная 32 Замыкание языка коммутативное 1!2 Запись правильной ситуации 268 ПРЕДМЕТМЫП УКЛЗАТЕЛЬ 360 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Запись простейшая (натурального числа) 34 Зацепленность (о шаге вывода) 31 — сильная 95 Значение грамматическое !6 — лексическое 16 Зона влияния (сечения) 96 Иерархизация 29! — допустимая 201 — обратная 190 — прямая 190 Изоморфизм (полугрупп) 316 Индекс ветвления (дерева вы. вола) приведенный 175 — грамматики, см. Емкость граллматики 57 — отношения эквивалентности 17 Инструкция 42 Интервал цепочки 21 — — несобственный 21 — — подстрелочный 299 — — — правильный 299 Итерация языка 23 — — усеченная 23 — Э-машины 164 Категория !85 — главная 186 — элементарная 185 †1 К-грамматика, см.
Грамматика категориальная 186 Класс, порожденный окрестностью 328 —, — семейством 328 — приведенный 337 Код грамматики 73 — цепочки 73 — Э.машины 258 Композиция Э-машин параллельная !64 — — последовательная 164 Коигруэиция 316 Конец дуги (в графе) 18 — — (в мультиграфе) 19 — пути 18 — цепочки 20 Конкатенация цепочек 20 Конкатенация языков, см. )тм. ножение языков, Произведение языков 22 Контекст в НС-правиле 29 — — — левый 29 — — — правый 29 Конфигурация 319 †3 — простая 321 Корень (дерева) !8 Коэффициент 24 КС-грамматика, см.
Грамматика бесконтекстная 29 КС-правило, см. Правило бесконтекстное 29 Куст узла !8 Левее (сс лежит левее 8; а расположена левее 8) 2! Лемма о замещении 96 — — сцеплении 64 — — — сильном 95 Лента входная 41 — конечного автомата !60 — рабочая 41 ЛЗ-сегмент, см. Сегмент лексически значимый 315 Лингвистика математическая 13 Мажорирование (функция у(П) нажорируется функцией й(п)) 59 Маркер граничный в Э-машине левый 42 — — — — правый 42 Машина с магазинной памятью (=МП-мап1ина) 137 — — — — нормальная !38 — — — — однодорожечная 168 — — — — однозначная 150 — — — — равномерная 169 — — — — с выходом 154 — — — — с ограниченным числом поворотов !7! — — — — — ! поворотами !71 — — — — счетчиковая 155 — — — — чисто стирающая 170 — Тьюринга с незластичной рабочей лентой ( =Н-машина) 52 Машина Тьюринга с иеэластичной рабочей лентой детерминированная (= ДН-машина) 53 — — — — — — одноленточная (=ОН-машина) 53 — — — — — — — детерминированная (=ДОН-машина) 53 — — — эластичной рабочей лентой ( =Э-машина) 41 — — — — — — без растяжения 85 — — — — — — детерминированная (=ДЭ-машина) 44 — — — — — — несамоприменимая 259 — — — — — — с ограниченным растяжением 87 — — — — — — самоприменимая 259 — — — — — — числовая 53 Между (8 лежит между а и у) 21 Меньше по порядку 97 Метаязык 1! Метка в дереве подчинения 298 — — системе составляющих 291 Многочлен 24 — замкнутый 24 Множество векторов 129 — — полулинейное 130 — натуральных чисел периодическое 181 — нумерационно рекурсивно перечислимое ( =н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
