Документ взят из кэша поисковой машины. Адрес оригинального документа : http://lib.mexmat.ru/books/10258
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 12:28:45 2016
Кодировка: Windows-1251
Гладкий А.В. - Формальные грамматики и языки :: Электронная библиотека попечительского совета мехмата МГУ
 
Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Гладкий А.В. - Формальные грамматики и языки
Гладкий А.В. - Формальные грамматики и языки

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

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



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

Название: Формальные грамматики и языки

Автор: Гладкий А.В.

Аннотация:

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


Язык: ru

Рубрика: Математика/

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$(B, \: \omega)$-дерево      117
$(B, \: \omega)$-дерево квазипростое      120
$(B, \: \omega)$-дерево простое      119
$P_1$-дерево      81; см. 'Дерево расположенное с помеченными узлами'
$P_2$-дерево      82; см. 'Дерево расположенное с помеченными узлами и дугами'
$\Delta$-грамматика      13
$\Delta$-грамматика окрестностная простейшая с порядком (=ПО-грамматика)      142
$\Delta$-грамматика окрестностная простейшая с порядком ограниченная      142
$\delta$-поддерево полное      120
$\Gamma$-образ языка      107
x-вычисление (Э-машины)      44
x-вычисление полное      44
x-ситуация заключительная      43
x-ситуация начальная      43
А-грамматика      29; см. 'Грамматика автоматная'
А-язык      30; см. 'Язык автоматный'
Автомат древообходящий (= Д-автомат)      140
Автомат конечный      159
Автомат конечный двуленточный (=ДК-автомат)      182
Автомат конечный с выходом      180
Алгоритм      252
Алгоритм для распознавания конечности Б-языка      124
Алгоритм для распознавания пустоты Б-языка      122
Алфавит      19 27;
Анализатор предсказуемостный      141
Б-грамматика      29; см. 'Грамматика бесконтекстная'
Б-ОАЕ-грамматика      234; см. 'Грамматика бесконтекстная ограниченной активной емкости'
Б-правило      29; см. 'Правило бесконтекстное'
Б-язык      30; см. 'Язык бесконтекстный'
База линейного множества векторов      129
База полулинейного множества векторов      130
Биграф      19
Биграф нагруженный      19
Буква      19; см. 'Символ элементарный'
Вектор      129
Вершина (графа)      18; см. 'Узел графа'
Взаимозамещаемость      318
Вкладываться (Б-грамматика вкладывается в Л-грамматику)      201
Вложена непосредственно (составляющая В непосредственно вложена в составляющую А)      286
Время работы (Э-машины)      63
Вхождение отмеченное      200
Вхождение символа      21
Вхождение цепочки      21
Вывод      28
Вывод бесповторный      31
Вывод полный      28
Вывод размеченный      28
Вывод размеченный упорядоченный      31
Вывод упорядочиваемый      31
Вывод, приведенный налево      51
Выводимость (цепочка $\eta$ выводима из $\omega$)      28
Выводимость непосредственная      28
Выводы равносильные      31; см. 'Равносильность выводов'
Выражение подстановочное      238
Выражение регулярное      24
Выражение регулярное замкнутое      24
Выражение центрально-подстановочное      177
Высота грозди      229
Высота Д-грамматики      207
Высота дерева      19
Высота системы составляющих      287
Высота составляющей      287
Высота узла (в дереве)      18
Вычисление (Э-машины)      43
Вычисляет (машина М вычисляет функцию f)      47
Вычитание (теоретико-множественное)      22
Глубина левая      57
Глубина правая      57
Гнездо      288
Гнездо однородное      242
Головка конечного автомата      160
Головка Э-машины входная      42
Головка Э-машины рабочая      42
Гомоморфизм      23; см. 'Отображение гомоморфное'
Гомоморфизм алфавитный      317
Гомоморфизм естественный      316
Грамматика      27; см. 'Грамматика порождающая'
Грамматика автоматная (=А-грамматика)      29
Грамматика автоматная k-определенная      180
Грамматика автоматная без омонимии      340
Грамматика автоматная обобщенная (=ОА-грамматика)      157
Грамматика автоматная обобщенная стандартная      158
Грамматика без растяжения      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
Грамматика конечно-автоматная      30; см. 'Грамматика автоматная'
Грамматика контекстно-неукорачивающая      250
Грамматика контекстно-свободная      29; см. 'Грамматика бесконтекстная'
Грамматика непосредственно (непосредственных) составляющих      29; см. 'Грамматика составляющих'
Грамматика неукорачивающая      84
Грамматика окрестностная простая      179
Грамматика порождающая      27
Грамматика почти неукорачивающая      88
Грамматика с конечным числом состояний      29; см. 'Грамматика автоматная'
Грамматика с ограниченной активной емкостью выводов (=ОАЕВ-грамматика)      174
Грамматика с ограниченным растяжением      87
Грамматика самопорождающая      279
Грамматика сильно сцепленная      95
Грамматика со стоп-правилами      51
Грамматика составляющих (=НС-грамматика)      29
Грамматика составляющих левоконтекстная      105
Грамматика составляющих обобщенная (=ОНС-грамматика)      113
Грамматика составляющих однозначная      83
Грамматика составляющих правоконтекстная      105
Грамматика составляющих с односторонним контекстом      105; см. 'Грамматика составляющих левоконтекстная' 'Грамматика
Грамматика сцепленная      64
Грамматика универсальная      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; см. 'Дерево синтаксического подчинения'
Дерево расположенное с помеченными узлами (=$P_1$-дерево)      81
Дерево расположенное с помеченными узлами и дугами ( =$P_2$-дерево)      82
Дерево расположенное с помеченными узлами и дугами линейное      168
Дерево расположенное с помеченными узлами линейное      168
Дерево синтаксического подчинения      294
Дерево синтаксического подчинения проективное      299
Дерево синтаксического подчинения размеченное      298
Дерево синтаксического подчинения слабо проективное      299
Дерево сокращения      189
Дерево составляющих      287
Диаграмма конечного автомата      160
Диаграмма линейной обобщенной бесконтекстной грамматики      182
Диаграмма обобщенной автоматной грамматики      158
ДК-автомат      182; см. 'Автомат конечный двулентрчный'
Длина вывода      28
Длина вычисления (Э-машины)      43
Длина пути      18
Длина цепочки      19
ДН-машина      53; см. 'Машина Тьюринга с неэластичной рабочей лентой детерминированная'
ДОН-машина      53; см. 'Машина Тьюринга с неэластичной рабочей лентой одноленточная детерминированная'
Дополнение      22
Допускать$^1$ (Э-машина допускает цепочку)      44
Допускать$^2$ (JXK-автомат допускает пару цепочек)      182
Достижимость (ситуация S' достижима из ситуации S в Э-машине)      43
Достижимость непосредственная      43
Дуга (в графе)      18
Дуга (в мультиграфе)      19
ДЭ-машина      44; см. 'Машина Тьюринга с эластичной рабочей лентой детерминированная'
Единица (полугруппы)      315
Емкость вывода активная      174
Емкость грамматики      57
Емкость грамматики активная      57
Емкость цепочки активная      174
Емкость Э-машины      63
Зависимость (в графе)      18
Зависимость символов (в бесконтекстной грамматике)      121
Задаваться      24; см. 'Представляться'
Заменяться (вхождение заменяется на 1-м шаге вывода)      28
Замещаемость      318
Замкнутость класса грамматик эффективная      32
Замыкание языка коммутативное      112
Запись правильной ситуации      268
Запись простейшая (натурального числа)      34
Зацепленность (о шаге вывода)      31
Зацепленность сильная      95
Значение грамматическое      16
Значение лексическое      16
Зона влияния (сечения)      96
Иерархизация      291
Иерархизация допустимая      201
Иерархизация обратная      190
Иерархизация прямая      190
Изоморфизм (полугрупп)      316
Индекс ветвления (дерева вывода) приведенный      175
Индекс грамматики      57; см. 'Емкость грамматики'
Индекс отношения эквивалентности      17
Инструкция      42
Интервал цепочки      21
Интервал цепочки несобственный      21
Интервал цепочки подстрелочный      299
Интервал цепочки подстрелочный правильный      299
Итерация Э-машины      164
Итерация языка      23
Итерация языка усеченная      23
К-грамматика      186; см. 'Грамматика категориальная'
Категория      185
Категория главная      186
Категория элементарная      185-186
Класс приведенный      337
Класс, порожденный окрестностью      328
Класс, порожденный семейством      328
Код грамматики      73
Код цепочки      73
Код Э-машины      258
Композиция Э-машин параллельная      164
Композиция Э-машин последовательная      164
Конгруэнция      316
Конец дуги (в графе)      18
Конец дуги (в мультиграфе)      19
Конец пути      18
Конец цепочки      20
Конкатенация цепочек      20
Конкатенация языков      22; см. 'Умножение языков' 'Произведение
Контекст в НС-правиле      29
Контекст в НС-правиле левый      29
Контекст в НС-правиле правый      29
Конфигурация      319-320
Конфигурация простая      321
Корень (дерева)      18
Коэффициент      24
КС-грамматика;      29 см. 'Грамматика бесконтекстная'
КС-правило      29; см. 'Правило бесконтекстное'
Куст узла      18
Левее ($\alpha$ лежит левее $\beta$; $\alpha$, расположена левее $\beta$)      21
Лемма о замещении      96
Лемма о сцеплении      64
Лемма о сцеплении сильном      95
Лента входная      41
Лента конечного автомата      160
Лента рабочая      41
ЛЗ-сегмент      315; см. 'Сегмент лексически значимый'
Лингвистика математическая      13
Мажорирование (функция g(n) мажорируется функцией h(n))      59
Маркер граничный в Э-машине левый      42
Маркер граничный в Э-машине правый      42
Машина с магазинной памятью (=МП-машина)      137
Машина с магазинной памятью нормальная      138
Машина с магазинной памятью однодорожечная      168
Машина с магазинной памятью однозначная      150
Машина с магазинной памятью равномерная      169
Машина с магазинной памятью с l поворотами      171
Машина с магазинной памятью с выходом      154
Машина с магазинной памятью с ограниченным числом поворотов      171
Машина с магазинной памятью счетчиковая      155
Машина с магазинной памятью чисто стирающая      170
Машина Тьюринга с неэластичной рабочей лентой (=Н-мащина)      52
Машина Тьюринга с неэластичной рабочей лентой детерминированная (=ДН-машина)      53
Машина Тьюринга с неэластичной рабочей лентой одноленточная (=ОН-машина)      53
Машина Тьюринга с неэластичной рабочей лентой одноленточная детерминированная (=ДОН-машина)      53
Машина Тьюринга с эластичной рабочей лентой (=Э-машина)      41
Машина Тьюринга с эластичной рабочей лентой без растяжения      85
Машина Тьюринга с эластичной рабочей лентой детерминированная ( = ДЭ-машина)      44
Машина Тьюринга с эластичной рабочей лентой несамоприменимая      259
Машина Тьюринга с эластичной рабочей лентой с ограниченным растяжением      87
Машина Тьюринга с эластичной рабочей лентой самоприменимая      259
Машина Тьюринга с эластичной рабочей лентой числовая      53
Между ($\beta$ лежит между $\alpha$, и $\gamma$)      21
Меньше по порядку      97
Метаязык      11
Метка в дереве подчинения      298
Метка в системе составляющих      291
Многочлен      24
Многочлен замкнутый      24
Множество векторов линейное      129
Множество векторов полулинейное      130
Множество натуральных чисел периодическое      181
Множество нумерационно рекурсивно перечислимое (=н. р. п. м.)      53
Множество опорное (формального ряда)      211
Множество рекурсивно перечислимое      49
Множество рекурсивно перечислимое числовое (=ч. р. п. м.)      53
Модель одноленточная прямая (=п. о. м.)      45
Модель парадигматическая      324
Модель синтагматическая      324
1 2 3
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2016
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте