Теория формальных грамматик - Гросс М.
Теория формальных грамматик
Автор: Гросс М.Другие авторы: Лантен А.
Издательство: М.: Мир
Год издания: 1971
Страницы: 296
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
Скачать:
ОГЛАВЛЕНИЕ COLLECTION PROGRAMMATION Publiee sous la direction de L. Nolin
publications de l'institut de programmation de la faculte des sciences de paris
NOTIONS SUR LES GRAMM AIRES FORMELLES
par
Maurice GROSS et Andrd LENTIN
Institut Blaise-Pascal
paris
GAUTHIER-VILLARS 1967 М. Гросс, A. Лантен
ТЕОРИЯ ФОРМАЛЬНЫХ ГРАММАТИК
Перевод с французского И. А. МЕЛЬЧУКА
Под редакцией А. В. ГЛАДКОГО
ИЗДАТЕЛЬСТВО «МИР» Москва 1971 УДК 450 512 8
Книга M Гросса и А Лантена посвящена одной из наиболее важных областей математической лингвистики — теории формальных грамматик Хомского. В первой части вводятся необходимые понятия из алгебры, математической логики и теории алгоритмов Во второй рассматриваются некоторые классы формальных языков; третья часть посвящена алгебраической трактовке языков и их свойств.
Написанная на достаточно высоком уровне строгости, книга в то же время является сравнительно легкой для чтения Она будет полезна широкому кругу читателей: математикам, желающим ознакомиться с математической лингвистикой, специалистам по программированию и вычислительной математике, лингвистам и всем специалистам, работающим в смежных областях.
Редакция литературы по математическим наукам
Инд. 2-2-3, 7-1-1
8-71 ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Предлагаемая вниманию читателя книга М. Гросса и А. Лан-тена — одно из первых в мировой литературе руководств по теории формальных грамматик. По замыслу авторов эта книга предназначается для первоначального изучения указанной теории и должна быть доступна читателю с минимальной математической подготовкой; поэтому ее содержание ограничено основными понятиями и теоремами, а изложение носит элементарный характер. В то же время — и это очень существенное достоинство книги — теория формальных грамматик излагается в ней не изолированно, а в широком контексте понятий теории алгоритмов и теории автоматов (а также некоторых алгебраических концепций), что позволяет читателю более глубоко понять содержание самой теории грамматик и составить представление о ее месте в кругу родственных математических дисциплин. Необходимые понятия (машины Тьюринга, комбинаторные системы, конечные автоматы и т. д.) излагаются в самой книге, так что она может служить и для ознакомления с первоначальными (но только первоначальными) понятиями теории алгоритмов и теории автоматов.
Вообще отбор и расположение материала представляются в целом весьма удачными. Здание книги спроектировано авторами превосходно. Если бы вдобавок ими была проявлена высокая требовательность к выбору материала, книга была бы безупречной. Но, к сожалению, это не так: в ряде мест качество отделочного, а кое-где и основного строительного материала оставляет желать лучшего. Доказательства в книге, как правило, неформальные; при указанном характере книги это, конечно, правильно, но иногда стремление к неформальности и простоте заводит авторов слишком далеко, и тогда теряется ясность, а то и корректность изложения. Попадаются и просто небрежно проведенные и даже ошибочные рассуждения, а также не вполне согласованные между собой места. Редактор и переводчик старались по мере сил испра- 6
Предисловие редактора перевода
вить эти дефекты — иногда с помощью примечаний, иногда посредством незначительных сокращений, а чаще путем внесения исправлений в текст (без специальных оговорок). Трудно судить, в какой мере нам это удалось, но, во всяком случае, мы устранили все замеченные нами неточности и несогласованности. Примечания сделаны и в ряде мест, так или иначе требовавших пояснения.
Можно надеяться, что книга окажется полезной специалистам различных профилей, которые пожелают ознакомиться с основами теории формальных грамматик, — математикам, специалистам по программированию, лингвистам (по крайней мере тем из них, которые не боятся читать элементарно написанные математические книги), а также специалистам в области автоматической обработки информации.
А. Гладкий ОТ АВТОРОВ
Настоящая книга написана на основе лекций, читанных авторами в ряде мест, из которых мы назовем здесь следующие: Центр количественной лингвистики факультета точных наук Парижского университета (созданный по инициативе покойного профессора Фавара); кафедра вычислительной математики того же факультета (профессор Рене де Поссель); кафедра математической физики Тулузского университета (профессор М. Лоде): курс для аспирантов по специальности «Обработка информации»; Отделение лингвистики Пенсильванского университета (профессор 3. С. Хэр-рис); Институт программирования факультета точных наук Парижского университета.
Задуманная и написанная как учебник, эта книга не претендует на научную оригинальность. Значительную часть материала мы почерпнули из таких фундаментальных, ныне уже классических работ, как книга М. Дэвиса [1958] и ряд статей Н. Хомского (в первую очередь см. Хомский [1963]). Перечислять все источники многочисленных заимствований, вполне естественных в учебнике, вряд ли целесообразно, и мы ограничимся указанием двух, наиболее полезных для нас. Это лекции Ж. Питра, читавшиеся им в упомянутом выше Центре количественной лингвистики, и работы М. Нива, посвященные теории кодирования и преобразованиям формальных языков.
