Гладкий - Формальные грамматики и языки - 1973 (947381), страница 69
Текст из файла (страница 69)
Показать, что для любого лексически размеченного языка ()г, ь, Г): а) 5-производная эквивалентность для отношения «принадлежать одному приведенному классу» совпадает с Ть 'г [Ревзин 1967, стр. 159]); б) зто отношение является укрупнением 8» тогда и только тогда, когда (У, Т» Г) однороден [Ревзин 1967, стр. 160]. ' БИБЛИОГРАФИЧЕСКИЕ ЭАМЕЧАНИЯ К главе 1. Понятие порождающей грамматики введено Н. Хомским [Сйопш1гу !956, 1957, 1959(а) *), 1963). (Родственное понятие «полутуэвской системы» рассматривалось в теории алгоритмов и раиыпе— см., например, [К!еепе 1952] "").) Им же введены понятия НС-грамматики, Б-грамматики и А-грамматики (см. укаэанные выше работы; Н.
Хомский пользуется терминами «грамматики класса !»для НС.грамматик, «грамматики класса 2» для Б-грамматик и «грамматики класса 3» для А-грамматик). Регулярные выражения введены С. Клини [К!еепе 1956]. Сигнализирующие функции детерминированных вычислений введены в 50-х гг. Г. С. Цейтнным (не опубликовано; см. [Яновская 1959, стр.
44, Трахтенброт 1967, стр. 9]) и независимо Б, А, Трахтенбротом [Трахтенброт 1956]. Общая теория сигнализирующих функций детерминированных вычислений — перенос ее идей на случай грамматик составляет основную часть содержания в 2.!в построена М. Блюмом [В!цш 1967]. Временная сложность и емкость для грамматик были введены — под влиянием идей Б.
А. Трахтенброта — в [Гладкий 1964(в), 1966], Понятия левой и правой глубины восходят к работе В. Ингве [Упйче 1960], понятие активной емкости — к работам Мэри Кэтрин Интемы [Уп[ешз 1967] и Б. Брейнерда [Вга!пегб 1967); в общйм виде последнее понятие сформулировано Э. Д. Стоцким [Стоик~6! 1969]. Понятие разброса введеяо в [Гладкий — Диковский !970). Лемма о сцеплении доказана для НС-грамматик в [Гладкий 1964(вН и распространена на общий случай в [Воой 1969].
Теорема 2.1 доказана для частного случая в [Гладкий 1963(в)]. Теорема 2,2 принадлежит Р. Буку [Воой 1969]. Теоремы 2.4 н 2.5 — это известные теоремы Г. С. Цейтина (см. [Яновская !959, стр, 45, Трахтенброт 1967, стр. 152]) н М. Рабина [ЯаЫп 1959*"), Трахтенброт 1967, стр. 194) из теории сложности вычислений, пере- *) Эта работа содержит неточности в определениях, впоследствии замеченные и исправленные К. Чуликом [Сц192 1965]. '") В русском переводе этой книги — «полусистема Туэ» (стр. 340). »"') В этой работе нет доказательства, БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ 345 песенные на случай грамматик. Приводимые нами доказательства этих теорем по существу заимствованы из книги [Трахтенброт 1967).
Изучению временной сложности грамматих посвящена книга [Воой 1969). К главе 3. Понятие дерева вывода восходит к основополагающим работам Н. Хомского [СЬошз!гу 1956, 1957, 1959(а), !963]. Ему же принадлежат понятие неукорачивающей грамматики и теорема 3.1 [СЬошзйу 1959(аЦ. Теорема 3.2, в несколько иной форме, доказана в [Кпгода 1964). Другое доказательство существования для всякой грамматики без растяжения эквивалентной ей НС-грамматвки (положенное в оашву доказательства теоремы 35) было дано в [Гладкий 1963(вЦ. Теорема 3.3 отмечена в [Гладкий 1966). (Эффективная) замкнутость класса НС-языков относительно пересечение доказана независимо в трех работах [Ьапбч'еЬег 1963, Гладкий !963(в), Кнгода !964).
Теорема 3.7 доказана в ]Гладкий 1964(вЦ. Использованная в ее доказательстве техника следов независимо разработана — применительно к детерминированным машинам Тьюринга — Б. А. Трахтенбратом [Трахтенброт !964), Я, М. Барздинем [Барздинь !965], М. Рабином [ЕаЫп 1963], Ф.
Хеппи [Непп(е 1965). Лемма 3.2 принадлежит фактически Б. А. Трахтенброту [Трахтенброт 1964). Пример, аналогичный примеру 1 из 6 3.4, был впервые построен Р. Парикхом [Раг!ЬЬ 196Ц. Примеры односторонних НС-грамматик, выводящих за пределы класса Б-языков, были указааы независимо Л. Хейнсом На!пез 1965['), Л. Г. Самойленко [Самойленко 1968[ и И. Гавелом Наче! 1969]. Теорема 3.8 доказана Л. Хейнсом [На!пез 1969, 1970]. К главе 4. Основные факты теории Б-языков были впервые систематизированы — и многие из них впервые получены — в статье [ВагН!11е! — Рег!ез — 55аш(г 196Ц.
В ней содержится прантически все изложенное в 66 4.1, 4.2, а также теорема 4.5 (и некоторые другие результаты, которые будут отмечены ниже). Большую роль в развитии теории Б-языков сыграла работа Р. Парикха [Раг!ЬЬ !96Ц "), в которой введено понятие однозначности языка и указан первый пример неоднозначного бесконтекстиого языка (прамер 3 из 5 4Л); там же доказана теорема 4.6. Теорема 4.7 доказзна в [Гладкий !965(бЦ.
Теорема 4.8 впервые опубликована, видимо, в [5сЬе!и. Ьегд 1960]; она имеется также в [Ваг-НШе! — Рег!ез — 3Ьаш1г 196Ц. Неоднозначность Б-языков изучалась в [О!пзбнге — ШВап 1966], где для важного в приложениях случая ограниченных языков (см. упражнение 5.32) получено необходимое и достаточное условие неоднозначности (соответствующие результаты изложены также в [О!пзЬнгп 1966, гл. 6]). Понятие МП-машины введено Н. Хомским [СЬошзйу- *) О существовании прамера, построенного в диссертации ]На!- лез !965[, автору стало известно из рукописи ]На!пез !970), любезно присланной ему Л. Хейисом в конце 1970 г. '*) Препринт, впоследствии перепечатанный в [Раг!ЬЬ 1966]. 1962) *); им же доказана теорема 4.9 [СЬогпз(су 1962, !963]. Впоследствии эта теорема несколько раз передоказывалась, в частности Р.
Эви [Етеу 1963] и Г. С. Пейтиным (ие опубликовано). Конструкции, используемые для ее доказательства в настоящей книге (леммы 432 — 4.14), навеяны идеями Ю. А. Шрейдера, В. Б. Борщева и М. В. Хомякова [Шрейдер 1969, Борщев — Хомяков 1970] и Л. С. Модиной [Мадина 1970].
Детерминированные МП-машины впервые рассмотрел М, Шютценберже [3«Ь5!хепЬегпег 1963)! они изучались также С. Гинзбургом н Ш. Грейбах [СбпзЬнгŠ— Оге!Ьасй 1966(бЦ и А. Я . Диковским [Диковский 1969]. Теория Б-языков посвящена книга [О!пзЬнгд 1966). К главе 5. Конечные автоматы в явной форме подвергаются систематическому изучению с 50-х гг. (их называют также «посз[едовательностными машинами», «автоматами Мура-Милна); однако в не. явном виде они рассматривались и раньше в теории алгоритмов (головка машины Тьюринга по существу представляет собой конечный автомат; см. [Тнг(пд 1936 — 1937[) и в теории информацчи (см., например, [3Ьаппоп 1948) '")).
Теорема 5.3 в неявном, виде установлена Ю. Т. Медведевым [Медведев !956); в явной форме впервые опубликована в [КаЫп — 3соИ 1959]. Регулярные языки введены в [К!еепе 1956]; там же отмечена (эффективная) замкнутость класса регулярных языков относительно основных операций и доказана теорема, по существу совпадающая с теоремой 5.6. Теорема 5.7 впервые появилась, по-видимому, в [МуЬШ 1957] и [Ь[егоде !958).
Изучению ОА- грамматик посвящена работа [СЬошайу — МШег !958]. Линейныс грамматики введены в [3сйй1гепЬегеег !96Ц, метаяннейные — либо в той же работе '*"), либо в [СЬошз1гу 1963] и [СЬошзйу — 3с!зй1хепЬег. Еег 1963) МП-машины с ограниченным числом поворотов и ОАЕВ- грамматики изучались в [О!пзЬнгб — Бран!ег !966); в этой работе доказаны теоремы 5.11 и 5.12.
К главе б. Категораальные грамматики появились значительно раньше всех других типов формальных грамматик; они были введены в работах С. Лесьневского [ьйап!етчзМ 1929] и Кс Айдукевнча [А[бнРбея1сх 1935] и предназнбчались для описания структуры формальных языков математики. Использовать категориальные грамматики для моделирования естественных языков предложил И. Бар.Хиллел [Ваг-Н!Бе1 1953); он же поставил вопрос о взаимоотношении между категориальными грамматиками и Б-грамматиками, который был ре- *) Сходные конструкции использовались ранее, на неформальном уровче, в теории программирования — см, например, [Внгйз— '1«'аггеп — %г!ЕМ 1954, 3аше1зоп — Ванег !960).
*') Стр. 313 русского перевода. «*') Автор не имел возможности с ней ознакомиться; приво. димые здесь сведения о ней заимствованы из [Огоеа — Ьеп!1п 1967). БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ 846 БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ 347 шеи Х. Гайфманом [Ваг-НП!е! — ОаИгпап — ЗЬаппг 1960]*). Позднее другое доказательство теоремы Х. Гайфмана об эквивалентности категорнальиых грамматик и Б-грамматик было дано А. Я. Диковским и Л. С. Модиной [Диковский — Модина 1968]'*). В настоящей книге излагается (с рядом модификаций) первоначальное доказательство Х. Гайфмана **»). Теорема о нормальной форме доказана Шейлой Грейбах ([Оге!Ьа«Ь 1965]; другое, более простое доказательство см.
[Оге!ЪасЬ 1967]). Простые доминационные грамматики (грамматики зависимостей) введены Д. Хейсом [Науа 196Ц. Их связь с Б-грамматиками была изучена в работе Х. Гайфмана [ОаПгпап 196Ц '*"), где доказана теорема, близкая к теореме 6.5. В приводи. мой здесь форме эта теорема дана С, Я. Фитиаловым [Фнтиалов 1968]; им же введено понятие степени грамматики (н степени системы составляющих). Доминационные грамматики общего вида введены М.
И. Белецким [Белецкий 1967]. Задание Б-языков с помощью нормальных систем уравнений предложено С. Гинзбургом н Г. Райсом [О1пзопгя РПсе 1962], с помощью формальных степенных рядов — М. Шютценберже [Зсйц!зепЬег8ег 1959, СЬошз)су — ЗсЬй(- хепЬегйег 1963]. Теорема 6.7 впервые опубликована, кажется, в [СЬошз(су — Зсйй!хепЬег8ег 1963]. К главе 7. Теоремы 7.1 и 7.2 в неявном виде фактически содержатся в [Хпете 1960); в явной форме теорема 7.1 впервые изложена, видимо, в [Шрейдер 1966]. Теорема 7.4 принадлежит Э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
