Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
К главе в.
Категориальные грамматики появились значительно раньше всех других типов формальных грамматик; они были введены в работах С. Лесьневского [Lasniewski 1929] и К,- Айдукевича [Ajdu-kiewicz 1935] и предназначались для описания структуры формальных языков математики. Использовать категориальные грамматики для моделирования естественных языков предложил И. Бар-Хиллел [Bar-Hillel 1953]; он же поставил вопрос о взаимоотношении между категориальными грамматиками и Б-грамматиками, который был ре-
*) Сходные конструкции использовались ранее, на неформальном уровне, в теории программирования — см., например, [Burks — Warren — Wright 1954, Samelson—Bauer 1960].
**) Стр. 313 русского перевода.
***) Автор не имел возможности с ней ознакомиться; приводимые здесь сведения о ней заимствованы из [Gross — Lentin 1967].
346
БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
шен X. Гайфманом [Bar-Hillel — Gaifman — Shamir I960]*). Позднее другое доказательство теоремы X. Гайфмана об эквивалентности категориальных грамматик и Б-грамматик было дано А. Я. Диков-ским и Л. С. Модиной [Диковский—Модина 1968]**). В настоящей книге излагается (с рядом модификаций) первоначальное доказательство X. Гайфмана***). Теорема о нормальной форме доказана Шейлой Грейбах ([Greibach 1965]; другое, более простое доказательство см. [Greibach 1967]). Простые доминационные грамматики (грамматики зависимостей) введены Д. Хейсом [Hays 1961]. Их связь с Б-грамматиками была изучена в работе X. Гайфмана [Gaifman 1961]****), где доказана теорема, близкая к теореме 6.5. В приводимой здесь форме эта теорема дана С. Я. Фитиаловым [Фитиалов 1968]; им же введено понятие степени грамматики (и степени системы составляющих). Доминационные грамматики общего вида введены М. И. Белецким [Белецкий 1967]. Задание Б-языков с помощью нормальных систем уравнений предложено С. Гинзбургом и Г. Райсом [Ginsburg —, Rice 1962], с помощью формальных степенных рядов— М. Шютценберже [Schutzenberger 1959, Chomsky — Schutzenberger 1963]. Теорема 6.7 впервые опубликована, кажется, в [Chomsky— Schutzenberger 1963].
К главе 7.
Теоремы 7.1 и 7.2 в неявном виде фактически содержатся в [Yngve I960]; в явной форме теорема 7.1 впервые изложена, видимо, в [Шрейдер 1966]. Теорема 7.4 принадлежит Э. Д. Стоцкому [Стоцкий 1969]. Теорема 7.5 доказана С. Гинзбургом и Э. Спеньером [Ginsburg — Spanier 1968]; в этой же работе впервые указаны примеры Б-языков сколь угодно большой активной емкости и Б-языка, не являющегося ОАЕ-языком (при этом существенным образом использованы результаты работы [Yntema 1967], где, в частности, построен пример Б-языка, не принадлежащего замыканию класса линейных языков относительно подстановки). Те же результаты получены независимо в [Диковский 1972 (а, б)] другим способом — с помощью введенного в этих же работах понятия густоты (там же доказана лемма 7.2). Приводимое нами доказательство теоремы 7.5 воспроизводит во всех основных чертах рассуждения из работ А. Я. Диковского; оттуда же взят (с некоторым видоизменением) пример 1 в § 7.2. Понятие самовставления и лемма 7.3 имеются уже в [Chomsky 1959(а, б)]. Теорема 7.6 (доказанная автором в процессе работы над книгой) представляет собой ответ на вопрос, поставленный С. Я. Фитиаловым.
*) В этой же работе, видимо, впервые появилось определение категориальной грамматики в принятой сейчас форме, а также самый термин «категориальная грамматика».
**) В 1966 г. X. Гайфман в устной беседе сообщил автору, что эта теорема была доказана также Н. Хомским. Однако в литературе упоминаний о доказательстве Н. Хомского обнаружить не удалось.
***) Доказательство А. Я. Диковского и Л. С. Модиной существенно проще, но опирается на теорему о нормальной форме. Автор счел более естественным обратный порядок изложения.
?***) Препринт, перепечатанный ^последствии в [Gaifman 1965].
БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
347
К главе 8.
Проблема распознавания самоприменимости машины Тьюринга явилась одной из первых алгоритмических проблем, для которых была доказана неразрешимость [Turing 1936—1937]. Теорема Райса также представляет собой один из классических результатов теории алгоритмов [Rice 1953]. Доказательства нераспознаваемости п классе НС-грамматик пустоты и конечности языка, а также неразрешимости проблемы эквивалентности НС-грамматик приведены в [Chomsky 1963] (со ссылкой на неопубликованную заметку С. Шайн-берга). Нераспозиаваемость бесконтекстности в классе НС-грамма-тик указана Э. Шамиром [Shamir 1962]. Теорема 8.3 доказана в [Гладкий 1964(6)]. Нераспозиаваемость в классе ОБ-грамматик свойств языка иметь пустое и конечное дополнение и быть ОА-язы-ком, а также неразрешимость проблемы эквивалентности Б-грамматик установлены в [Bar-Hillel — Perles — Shamir 1961] с помощью теоремы Поста (см. упражнение 8.14). Техника протоколов (лемма 8.5) предложена в [Гладкий 1965(a)] (и независимо в [Hartmanis
1967]). Нераспозиаваемость неоднозначности Б-языков доказана независимо в [Гладкий 1965(6)] и [Ginsburg — Ullian 1966]*). Теорема 8.5 установлена (в несколько иной форме) Ш. Грейбах [Grei-bach 1968]. Неразрешимость для бесконтекстных и линейных языков проблем распознавания замещаемости, взаимозамещаемости и конфигураций доказана в [Гладкий 1965(a)].
