|
Теория формальных грамматик |
Гросс М., Лантен А. |
год издания — 1971, кол-во страниц — 296, язык — русский, тип обложки — твёрд. 7Б тканев., масса книги — 380 гр., издательство — Мир |
|
цена: 600.00 руб | | | | |
|
Сохранность книги — хорошая
COLLECTION PROGRAMMATION Publiée sous la direction de L. Nolin PUBLICATIONS DE L'INSTITUT DE PROGRAMMATION DE LA FACULTE DES SCIENCES DE PARIS NOTIONS SUR LES GRAMMAIRES FORMELLES par Maurice GROSS et André LENTIN Institut Blaise-Pascal
PARIS GAUTHIER-VILLARS 1967
Пер. с фр. И. А. Мельчука
Формат 60x90 1/16. Бумага типографская №2 |
ключевые слова — лингвист, грамматик, алгебр, логик, алгоритмов, автомат, тьюринг, комбинатор, полугрупп, язык, высказыван, алфавит, вычислимост, гёдел, контекстно-свободн, кс-язык, мп-автомат, а-грамматик, гомоморфизм |
Книга М. Гросса и А. Лантена посвящена одной из наиболее важных областей математической лингвистики — теории формальных грамматик Хомского. В первой части вводятся необходимые понятия из алгебры, математической логики и теории алгоритмов. Во второй рассматриваются некоторые классы формальных языков; третья часть посвящена алгебраической трактовке языков и их свойств.
Написанная на достаточно высоком уровне строгости, книга в то же время является сравнительно лёгкой для чтения. Она будет полезна широкому кругу читателей: математикам, желающим ознакомиться с математической лингвистикой, специалистам по программированию и вычислительной математике, лингвистам и всем специалистам, работающим в смежных областях.
Предлагаемая вниманию читателя книга М. Гросса и А. Лантена — одно из первых в мировой литературе руководств по теории формальных грамматик. По замыслу авторов эта книга предназначается для первоначального изучения указанной теории и должна быть доступна читателю с минимальной математической подготовкой; поэтому её содержание ограничено основными понятиями и теоремами, а изложение носит элементарный характер. В то же время — и это очень существенное достоинство книги — теория формальных грамматик излагается в ней не изолированно, а в широком контексте понятий теории алгоритмов и теории автоматов (а также некоторых алгебраических концепций), что позволяет читателю более глубоко понять содержание самой теории грамматик и составить представление о её месте в кругу родственных математических дисциплин. Необходимые понятия (машины Тьюринга, комбинаторные системы, конечные автоматы и т. д.) излагаются в самой книге, так что она может служить и для ознакомления с первоначальными (но только первоначальными) понятиями теории алгоритмов и теории автоматов.
Вообще отбор и расположение материала представляются в целом весьма удачными. Здание книги спроектировано авторами превосходно. Если бы вдобавок ими была проявлена высокая требовательность к выбору материала, книга была бы безупречной. Но, к сожалению, это не так: в ряде мест качество отделочного, а кое-где и основного строительного материала оставляет желать лучшего. Доказательства в книге, как правило, неформальные; при указанном характере книги это, конечно, правильно, но иногда стремление к неформальности и простоте заводит авторов слишком далеко, и тогда теряется ясность, а то и корректность изложения. Попадаются и просто небрежно проведённые и даже ошибочные рассуждения, а также не вполне согласованные между собой места. Редактор и переводчик старались по мере сил исправить эти дефекты — иногда с помощью примечаний, иногда посредством незначительных сокращений, а чаще путём внесения исправлений в текст (без специальных оговорок). Трудно судить, в какой мере нам это удалось, но, во всяком случае, мы устранили все замеченные нами неточности и несогласованности. Примечания сделаны и в ряде мест, так или иначе требовавших пояснения.
Можно надеяться, что книга окажется полезной специалистам различных профилей, которые пожелают ознакомиться с основами теории формальных грамматик, — математикам, специалистам по программированию, лингвистам (по крайней мере тем из них, которые не боятся читать элементарно написанные математические книги), а также специалистам в области автоматической обработки информации.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Л. Гладкий
|
ОГЛАВЛЕНИЕПредисловие редактора перевода | 5 | От авторов | 7 | Предисловие | 9 | | ЧАСТЬ I. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ЛОГИКИ И АЛГЕБРЫ | | Глава I. Слова (цепочки). Полугруппы. Языки | 13 | | § 1.1. Свободная полугруппа | 13 | § 1.2. Операции над словами | 18 | § 1.3. Языки | 23 | § 1.4. Упражнения | 26 | | Глава II. Общие сведения о формальных системах | 30 | | § 2.1. Описание исчисления высказываний на интуитивном уровне | 30 | § 2.2. Понятие формальной системы | 37 | § 2.3. Формализованный вариант исчисления высказываний | 42 | § 2.4. Определение формальной системы | 46 | | Глава III. Комбинаторные системы | 49 | | § 3.1. Определение комбинаторных систем | 49 | § 3.2. Нормальные системы | 57 | § 3.3. Упражнения | 61 | § 3.4. Независимость от алфавита | 61 | | Глава IV. Алгоритмы. Машины Тьюринга | 64 | | § 4.1. Алгоритмы | 64 | § 4.2. Машины Тьюринга | 68 | § 4.3. «Численные» машины Тьюринга | 76 | § 4.4. Упражнения | 79 | | Глава V. Вычислимость и разрешимость | 81 | | § 5.1. Исчисление функций | 81 | § 5.2. Операции над функциями | 83 | § 5.3. Метод Гёделя | 86 | § 5.4. Рекурсивные и рекурсивно перечислимые множества | 89 | § 5.5 Замечания и дополнения | 93 | | Глава VI. Комбинаторные системы и машины Тьюринга: неразрешимые | проблемы | 99 | | § 6.1. Комбинаторные системы и машины Тьюринга | 99 | § 6.2. Неразрешимые проблемы | 105 | | ЧАСТЬ II. НЕКОТОРЫЕ ЗАМЕЧАТЕЛЬНЫЕ КЛАССЫ ЯЗЫКОВ | | Глава VII. Контекстно-свободные языки (языки Хомского): общая | характеристика и основные свойства | 112 | | § 7.1. Грамматика и описание синтаксических структур | 112 | § 7.2. Определения. Распознаваемые свойства | 116 | § 7.3. Свойства замкнутости | 123 | § 7.4. Специальные классы КС-языков | 126 | § 7.5. Упражнения | 129 | | Глава VIII. Нераспознаваемые свойства КС-грамматик | 130 | | § 8.1. Проблемы, связанные с пересечением | 130 | § 8.2. Проблемы, связанные с неоднозначностью | 133 | § 8.3. Существенная неоднозначность минимальных линейных языков | 139 | | Глава IX. Автоматы с магазинной памятью | 143 | | § 9.1. Автоматы, допускающие языки | 143 | § 9.2. Автоматы, порождающие языки | 149 | § 9.3. Класс языков, допускаемых (порождаемых) МП-автоматами | 151 | § 9.4. Приложения КС-языков | 155 | | Глава X. Автоматные языки и конечные автоматы | 169 | | § 10.1. А-грамматики | 159 | § 10.2. Конечные автоматы | 162 | § 10.3. Некоторые обобщения и видоизменения конечных автоматов | 166 | § 10.4. Свойства замкнутости. Представление А-языков по Клини | 168 | § 10.5. А-языки и КС-языки | 171 | § 10.6. Односторонние конечные преобразователи | 172 | | Глава XI. Задание языков с помощью систем уравнений | 175 | | § 11.1. Функции, аргументами и значениями которых являются языки | 175 | § 11.2. Языки и формальные степенные ряды | 189 | | Глава XII. Грамматики непосредственно составляющих. Автоматы с линейно | ограниченной памятью | 194 | | § 12.1. Грамматики непосредственно составляющих (НС-грамматики) | 194 | § 12.2. Линейно ограниченные автоматы | 196 | § 12.3. Классификация автоматов | 199 | § 12.4. Упражнения | 201 | | ЧАСТЬ III. АЛГЕБРАИЧЕСКИЙ ПОДХОД | | Глава XIII. Гомоморфизмы полугрупп | 202 | | § 13.1. Произвольные полугруппы | 202 | § 13.2. Конгруэнция и эквивалентности, сопоставляемые языку | 207 | § 13.3. Понятия, связанные с кодами | 212 | | Глава XIV. Дополнительные сведения об автоматных языках | 214 | | § 14.1. Стандартные А-языки | 214 | § 14.2. Свойства стандартных А-языков | 217 | § 14.3. Алгебраическое описание А-языков | 218 | § 14.4. Преобразования | 226 | | Глава XV. Дополнительные сведения о КС-языках | 232 | | § 15.1. Языки Дика | 232 | § 15.2. Стандартные КС-языки | 240 | § 15.3. Совпадение класса КС-языков с классом языков, допускаемых | автоматами с магазинной памятью | 244 | § 15.4. Упражнения | 245 | | Глава XVI. Алгебраические языки | 247 | | § 16.1. Дополнительные сведения о формальных степенных рядах | 247 | § 16.2. Алгебраические ряды | 257 | § 16.3. Приложения к языкам | 259 | § 16.4. Упражнения | 264 | § 16.5. Применение «языковых» уравнений в комбинаторной геометрии | 264 | | ПРИЛОЖЕНИЕ. ТРАНСФОРМАЦИОННЫЕ ГРАММАТИКИ | | § 1. Формальные грамматики и естественные языки | 272 | § 2. КС-грамматики и трансформации | 274 | § 3. Расширение грамматики | 275 | § 4. Проблемы, связанные с трансформациями | 281 | | Избранная библиография | 287 |
|
Книги на ту же тему- Трансляция языков программирования, Вайнгартен Ф., 1977
- Математическая лингвистика, Шаумян С. К., ред., 1973
- Алгебра. Языки программирования. — 2-е изд., перераб., Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л., 1978
- Жемчужины теории формальных языков, Саломаа А., 1986
- Определение языков программирования интерпретирующими автоматами, Оллонгрен А., 1977
- Равенство, сходство, порядок, Шрейдер Ю. А., 1971
- Зарубежные исследования по семиотике фольклора: Сборник статей, Мелетинский Е. М., Неклюдов С. Ю., сост., 1985
- Введение в прикладную комбинаторику, Кофман А., 1975
- Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
- Алгоритмы и вычислительные автоматы, Трахтенброт Б. А., 1974
- Логический подход к искусственному интеллекту: от классической логики к логическому программированию, Тей А., Грибомон П., Луи Ж., Снийерс Д., Водон П., Гоше П., Грегуар Э., Санчес Э., Дельсарт Ф., 1990
- Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И. А., Максимова Л. Л., 1975
- Теория алгоритмов: основные открытия и приложения, Успенский В. А., Семёнов А. Л., 1987
- Нечёткие множества в моделях управления и искусственного интеллекта, Аверкин А. Н., Батыршин И. 3., Блишун А. Ф., Силов В. Б., Тарасов В. Б., 1986
- Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
- Математическая логика, Клини С. К., 1973
- Элементарное введение в абстрактную алгебру, Фрид Э., 1979
- Алгебра, Ленг С., 1968
- Введение в алгебру. Часть III. Основные структуры: Учебник для вузов. — 2-е изд., исправл., Кострикин А. И., 2001
- Булевы алгебры, Сикорский Р., 1969
- Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры, Кокс Д., Литтл Д., О'Ши Д., 2000
- Адаптация и обучение в автоматических системах, Цыпкин Я. З., 1968
- Основы кибернетики, Джордж Ф., 1984
- Сравнительное изучение языков программирования, Хигман Б., 1974
- Программирование на современных алгоритмических языках: Учебное пособие для втузов.— 3-е изд., перераб. и доп., Пярнпуу А. А., 1990
- Языки программирования. Практический сравнительный анализ, Бен-Ари М., 2000
- Язык, Блумфилд Л., 1968
- Новое в лингвистике. Выпуск IV, Звегинцев В. А., сост., 1965
- Трёхмерная стратификационная модель языка и его функционирования: к общей теории лингвистических моделей, Шаляпина З. М., 2007
- Текст, машина, человек, Пиотровский Р. Г., 1975
|
|
|