Гинзбург С. — Математическая теория контекстно-свободных языков :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Гинзбург С. — Математическая теория контекстно-свободных языков

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Математическая теория контекстно-свободных языков

Автор: Гинзбург С.

Аннотация:

В книге достаточно полно изложены основные понятия и результаты теории контекстно-свободных грамматик и языков, прослеживаются ее связи с теорией автоматов, языками программирования, лингвистикой и машинным переводом.
Имеется большое число упражнений самой различной трудности, которые в совокупности существенно дополняют основной текст книги.
Книга окажется полезной математику, желающему ознакомиться с теорией формальных грамматик и ее связями с другими математическими теориями.

Язык:

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1970

Количество страниц: 328

Добавлена в каталог: 16.03.2007

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

d-допускаемый (d-accepted)      110
n-компонентная стандартная функция (n-tuple standard function)      29
Автомат (automaton)      72
Автомат конечный (finite-state acceptor)      72
Автомат линейно ограниченный (ЛО-автомат) (linear bounded acceptor)      107
Автомат недетерминированный конечный (nondeterministic finite-state acceptor)      76
Автомат с магазинной памятью (МП-автомат) (pushdown acceptor)      89
Аддитивная операция (additive operation)      152
Алгоритм (algorithm)      164
Алгоритмически неразрешимый (recursively unsolvable)      164
Алгоритмически разрешимый (recursively solvable)      164
Алфавит (alphabet)      13
Бинарная стандартная форма (binary standard form)      41
Вектор $\omega$ -максимальный ( $\omega$ - maximal)      287
Вектор (vector)      17
Вершина (node)      16
Вершина максимальная (maximal)      44
Вершина немаксимальная (non maximal)      44
Вершина пути (node in path)      16
Взаимно простые числа (relatively prime integers)      18
Вспомогательный символ самовставляющийся (self-embedding variable)      83
Вывод (derivation, generation)      22
Вывод левосторонний (leftmost)      50
Вывод правосторонний (rightmost)      50
Вывода длина (length of derivation)      22
Гомоморфизм (гомоморфное отображение) (homomorphism)      57
Грамматика контекстно-ограниченная (context-bounded grammar)      198
Грамматика контекстно-свободная (КС-грамматика) (context-free grammar)      34
Грамматика леволинейная (left-linear)      79
Грамматика минимальная линейная (minimal linear)      198
Грамматика непосредственно составляющих (НС-грамматика) (context-sensitive grammar)      23
Грамматика обобщенная порождающая (unrestricted rewriting)      105
Грамматика операторная (operator)      26
Грамматика порождающая (система подстановок) (phrase-structure)      21
Грамматика последовательностная (sequential)      82
Грамматика праволинейная (right-linear)      79
Грамматика с отношением предшествования (precedence)      26
Грамматический элемент (grammatical element)      56
Грамматический элемент заключительный (terminal)      57
Грамматического элемента структура (structure of a grammatical element)      57
Граф конечный ориентированный (finite directed graph)      16
Граф нагруженный (labeled)      16
Делитель наибольший общий (greatest common divisor)      18
Дерево вывода (generation tree)      42
Дерево вывода минимальное (minimal)      44
Дерево конечное корневое ориентированное с помеченными вершинами (finite rooted directed tree with labeled nodes)      17
Дерево составляющих (parsing tree)      42
Дополнение (complement)      13
Допускаемый (accepted)      73 76 92 107
Дуга (графа) (directed line)      16
Зависимость (одного вспомогательного символа от другого) (dependency)      36
Зеркальный образ (обращение) (цепочки) (reflection)      35
Индекс (index)      77
Класс эквивалентности (equivalence class)      14
Конец (заключительный отрезок) пути (terminal sub path)      16
Конец цепочки (terminal subword)      14
Конкатенация (concatenation)      13
КОРЕНЬ (ROOT)      17
Коэффициент (coefficient)      28
КС-грамматика линейная (linear grammar)      78
КС-грамматика металинейная (metalinear)      82
КС-грамматика неопределенная (ambiguous)      50
КС-грамматика неукорачивдюдпая (e-free)      60
КС-грамматика определенная (unambiguous)      50
КС-грамматика приведенная (reduced)      38
КС-грамматика равномерно ограниченной активной емкости (nonterminal bounded)      78
КС-грамматика с самовставлением (self-embedding)      80
КС-язык c-конечный (c-finite)      88
КС-язык детерминированный (deterministic language)      109
КС-язык линейный (linear)      78
КС-язык металинейный (metalinear)      82
КС-язык определенный (unambiguous)      52
КС-язык существенно неопределенный (inherently ambiguous)      52
Лемма о зависимости (dependency lemma)      36
Лента магазинной памяти (pushdown tape)      89
Линейно зависимый (linearly dependent)      17
Линейно независимый (independent)      17
ЛО-автомат детерминированный (deterministic linear bounded acceptor)      118
Магазинная память (pushdown store)      89
Маркер магазинной памяти (start pushdown symbol)      89
Множества непересекающиеся (disjoint sets)      13
Множество (регулярное) второго класса (regular set of class 2)      21 88
Множество коммутативное (commutative set)      239
Множество линейное (векторов) (linear)      204
Множество ограниченное (bounded)      200
Множество периодическое (ultimately periodic)      16
Множество полулинейное (semilinear)      204
Множество Пресбургера (Presburger)      260
Множество пустое (empty)      12
Множество расслоенное (stratified)      225
Множество регулярное (regular)      73 282
Множество рекурсивное (recursive)      166
Множество частично упорядоченное (partially ordered)      14
МП-автомат (pushdown acceptor, pda)      89
МП-автомат детерминированный (deterministic)      108
МП-автомат детерминированный без циклов (loop-free)      111
МП-автомат квазидетерминированный (quasi-deterministic)      109
МП-автомат обобщенный (generalized)      93
МП-автомат определенный (unambiguous)      102
МП-преобразователь (pushdown transducer, pdt)      147
Наименьшая неподвижная точка (minimal fixed point)      34
Начало (начальная подцепочка) (initial subword)      14
Не более чем счетное (множество) (denumerable)      15
Несчетное (множество) (nondenumerable)      15
Нормальная форма Бэкуса (Backus normal form)      27

НС-язык (context-sensitive language)      23
Обратный (для некоторого последовательностного преобразователя) последовательностный преобразователь (inverse of a sequential transducer)      137
Обращение (цепочки) (зеркальный образ) (цепочки) (reverse)      35
Объединение (теоретико-множественное) (set union)      12
Ограниченное удлинение (bounded output)      140
Операция (operation)      15
Оптимальная перетасовка (alternate shuffle)      155
Отношение (relation)      14
Отношение конгруэнтности (congruence relation)      77
Отношение эквивалентности (equivalence relation)      14
Отображение (mapping)      15
Отображение биаддитивное (biadditive function)      54
Отображение в (function into)      15
Отображение взаимно однозначное (one-to-one function)      15
Отображение линейное (linear function)      250
Отображение на (function onto)      15
Переменная (вспомогательный символ) (variable)      21
ПЕРЕСЕЧЕНИЕ (INTERSECTION)      12
Пересечение теоретико-множественное (set intersection)      12
Период (period)      203
Поддерево, порожденное вершиной (subtree generated by a node)      45
Подмножество (subset)      12
Подстановка (substitution)      57
Подцепочка (subword)      14
Пометка (label)      17
Пометка при вершине (node name)      17
Порождать (язык) (generate)      23
Порядок линейный (simple order)      15
Порядок частичный (partial)      14
Последовательность периодическая (ultimately periodic sequence)      16
Правило (production)      21
Правило левобуквенное (left-literal)      107
Правило леволинейное (left-linear)      79
Правило линейное (linear)      78
Правило подстановки (rewriting rule)      21
Правило праволинейное (right-linear production)      79
Предложение Пресбургера (Presburger sentence)      260
Предпериод (constant)      203
Преобразование конечное (generalized sequential machine mapping)      135
Преобразование последовательностное (sequential transducer mapping)      131
Преобразователь конечный (generalized sequential machine, gsm)      134
Преобразователь последовательностный (seguential transducer)      130
Преобразователь с магазинной памятью (МП-преобразователь) (pushdown transducer)      147
Преобразователь синхронный конечный (complete sequential machine)      134
Проблема соответствий (correspondence problem)      172
Продолжение вершины (extension of a node)      44
Произведение декартово (Cartesian product)      14
Производимый (выводом, деревом) (realized)      43
Производная (derivative)      156
Прямое произведение множеств ((complex) product of sets)      13
Прямое произведение цепочек (конкатенация) ((complex) product of words)      13
Пути длина (length of path)      16
Путь (path)      16
Разрешающая процедура (decision procedure, recursive solution, algorithm)      165
Реализуемый (realized)      22 90 148
Решение (solution)      29
Решение минимальное положительное (minimal positive)      253
Решение положительное (positive)      251
Свободная полугруппа (free semigroup)      14
Символ вспомогательный (переменная) (nonterminal)      21
Символ входной (input)      72 76 89 130 134
Символ выходной (output)      130 134 147
Символ магазинной памяти (pushdown symbol)      89
Символ начальный (аксиома) (axiom)      21
Символ основной (буква) (letter)      21
Система подстановок (порождающая грамматика) (rewriting system)      21
Согласованные (МП-автомат и МП-преобразователь) (associated pda and pdt)      119
Содержать последовательность (contain a sequence)      209
Состояние (state)      72 76 79 130 134
Состояние заключительное (final)      72 76 90
Состояние начальное (start)      72 76 89 131 134
Стандартная функция (standard function)      28
Счетное (множество) (denumerably infinite)      15
Такт (move)      90
Тасующая функция (shuffle)      155
Теорема о конечном преобразовании (gsm mapping theorem)      135
Теорема о пересечении (intersection)      125
Теорема о подстановке (substitution)      57
Теорема о разности (difference)      128
Теорема Парика (Parikh)      207
Теорема Поста о проблеме соответствий (Post correspondence)      161
Формальный полином (formal polynomial)      56
Формула Пресбургера (Presburger formula)      259
Функция выходов (output function)      134
Функция переходов (next-state)      72
Цепочка (word)      13
Цепочка в алфавите $\Sigma$ ( $\Sigma$ -word)      13
Цепочка длины k (word of length к)      13
Цепочка непустая (non- $\varepsilon$ word)      13
Цепочка полинома (word of polynomial)      56
Цепочка производимая путем (label of path)      17
Цепочка пустая (empty word)      13
Частное левое (left quotient)      156
Частное правое (right)      154
Член (функции) (term)      28
Элемент максимальный (maximal element)      15
Элемент минимальный (minimal)      15
Элементы несравнимые (incomparable elements)      15 231
Язык бесскобочный (parenthesis-free language)      56
Язык Дикка (Dyck)      26
Язык контекстно-свободный (КС-язык) (context-free)      24
Язык последовательностный (sequential)      82
Язык праволинейный (right-linear)      79
Язык с конечным числом состояний (finite-state)      75
Язык типа АЛГОЛ (ALGOL-like)      29
Язык, порождаемый грамматикой (phrase-structure)      23

О проекте