Гладкий - Формальные грамматики и языки - 1973 (947381), страница 70
Текст из файла (страница 70)
Д. Стоцкому Стоцкий 1969]. Теорема 7.5 доказана С. Гинзбургом и Э. Спеньером О!пзйпге — Зрап(ег 1968]; в этой же работе впервые указаны примеры Б-языков сколь угодно большой активной емкости н Б-языка, ие являющегося ОАВ-языком (при этом существенным образом использованы результаты работы [Хп!еша 1967], где, в частности, построен пример Б-языка, не принадлежащего замыканию класса линейных языков относительно подстановки). Те же результаты получены независимо в [Диковский 1972 (а, бЦ другим способом — с помощью введенного в этих же работах понятия густоты (там же доказана лемма 7.2).
Прииодимое нами доназательство теоремы 7.5 воспроизводит во всех основных чертах рассуждения иэ работ А. И. Диковского; оттуда же взят (с некоторым видоизменением) пример 1 в 5 7.2. Понятие самовставления н лемма 7.3 имеются уже в [СЬошзйу 1959(а, бЦ. Теорема 7.6 (доказанная автором в процессе работы над книгой) представляет собой ответ на вопрос, поставленный С. Я. Фитиаловым. ") В этой же работе, видимо, впервые появилось определение категориальной грамматики в принятой сейчас форме, а также самый термин «категориальная грамматика».
'") В 1966 г, Х. Гайфман в устной беседе сообщил автору, что эта теорема была доказана также Н. Хомским. Однако в литературе упоминаний о доказательстве Н. Хомского обнаРужить не удалось. "*) Доказательство А. Я, Диковского и Л. С. Модиной существенно проще, но опирается на теорему о нормальной форме. Автор счел более естественным обратный порядок изложения. » "*') Препринт, перепечатанный впоследствии в [Оа(!шап 1965].
К главе 8. Проблема распознавания самоприменимости машины Тьюринга явилась одной из первых алгоритмических проблем, для которых была доказана неразрешимость [ТпБпд 1936 — 1937]. Теорема Райса также представляет собой один из нлассических результатов теории алгоритмов [ВПсе 1953]. Доказательства нераспознаваемости в классе НС-грамматик пустоты и конечности языка, а также неразешнмости проблемы эквивалентности НС-грамматик приведены в СЬопЫу 1963] (со ссылкой на неопубликованную заметку С. Шайнберга).
Нераспознаваемость бесконтекстности в классе ЙС-грамматик указана Э. Шамиром [ЗЬапцг 19621 Теорема 8.3 доказана в [Гладкий 1964(б)]. Нераспозиаваемость в классе ОБ-грамматик свойств языка иметь пустое и конечное дополнение и быть ОА-языком, а также неразрешимость проблемы эквивалентности Б-грамматик установлены в [Ваг-Нйе! — Рег!ез — ЗЬагп1г 196Ц с помощью теоремы Поста (см.
упражнение 8.!4). Техника протоколов (лемма 8.5) предложена в [Гладкий 1965(а)] (и независимо в [Наг!шап(э 1967]). Нераспознаваемость неоднозначности Б-языков доказана не. зависимо в [Гладкий 1965(бЦ и [СбпзЬпгй — 1ЛПап 1966]*). ТеоУ ема 8.5 установлена (в несколько иной форме) Ш. Грейбах [Оге1- асЬ 1968!. Неразрешимость для бесконтекстных и линейных языков проблем распознавания замещаемости, взаимозамещаемости и конфигураций доказана в [Гладкий 1965(аЦ.
К приложению 1. Понятие системы составляющих восходит к грамматической традиции английского языка и американскому структурализму («анализ по непосредственным составляющим»; см. [В!оошПе!б 1933], [Наггга !96Ц и в особенности [ХуеПз 1947]). Понятия степени левого и правого ветвления идут от работы В. Интзе [Хинте 1960]; строго формально эти понятия впервые введены, видимо, в [Ваг-Н!Пе) — Казйег — ЗЬаш(г 1963]. Понятие степени гнездования введено Н. Хомским [СЬошз(су 196Ц; мы пользуемся этим понятием в видоизмененной форме, данной в [Ваг-НП1е! — КазЬег — ЗЬаш(г 1963] (эта форма не равносильна первоначальной). Понятие дерева синтаксического подчинения восходит к русской грамматической традиции; в явном виде оио впервые появилось (как часть некоторого более сложного понятия) у Л.
Теньера [Тези!Аге 1959). Идеи, приведшие к понятиям проективности и слабой проективности, впервые были — в неявной форме — высказаны Г. С, Цейтиным (см. [Цейтин — Засорина 196Ц) и независимо К. Харпером и Д. Хейсом [Нагрег — Науа 1960]. В явном виде эт понятия ввели, независимо друг от друга, И.
Лесерф [1.есег! 1960я" М. И. Белецкий [Белецкий 196Ц и С. Я. Фитналов [Фитиалов 1962]. (Общепринятые сейчас формулировки, приводимые и в настоящей княгц принадлежат С. Я. Фитиалову.) Проективиость изучалась с формальной и лингвистической точек зрения, в частности, в [Белецкий — Григорян — Заславский 1963], ') Содержание этой статьи наложено также в нниге [О!пзЬцгй 1966] (гл. 6). Биплиогрхфичяскин зАМБЧАит!й 348 К приложению П.
ЛИТЕРАТУРА [Дрейзин !963], [Иорданская 1967). Описанный в 6 П!. 3 способ уста- новления соответстввя между системами составляющих и деревьями подчинеаия указан в [Падучева !964] (в неформальном виде; форма- лизованное изложение — в [Гладкий 1966]). Начало теории замещаемости было положено работой [Кулагина 1958]. В этой работе было, в частности, введено понятие конфигурации, Определение конфигурации, изложенное в настоящей книге, — основанное на тех же идеях, что и первоначальное определение О. С. Кулагиной, но не равносильное ему, — дано в [Гладкий 1963(а)]; там же введены понятия конфигурационных характеристик и конечно характеризуемого языка и получены теоремы П!1. 1 и ПП.2 *). Еще одно видоизменение понятия конфигурации было предложено М. Навотным [г(ото(пу 1965(а,б,в)).
Лингвистическая критика конфигурационной модели имеется в [Падучева 1965], стимулированное в значительной степени этой критикой распространение понятия конфигурации на «языки деревье⻠— в [1Цербакоэа 1971]. Все основные понятия 6 ПП. 3 введены в [Кулагина !958); там же' доказаны теоремы ПП. 3 — ПП. 6. Алгебраическое изложеш1е этих понятий и результатов было дано Д. Н, Ленским [Ленской 1962] '") и М. Новотным [Новотный 1965].
Приведенные классы были введены (под именем «подклассов») И. И. Ревзиным [Ревзин 1962, 1967]. Анализирующим моделям посвящена книга [Магсцз 1967], их лингвистическим приложениям — [Ревзин 1967]. *) При понимании конфигураций в смысле первоначального определения эти теоремы не имеют места. »») На языке алгебры бинарных отношений (см, также [Шрейдер 19?О]). Б а рад и н ь Я. М. Сложность распознавания симметрии на машинах Тьюринга. — Сб.
«Проблемы кибернетики», вып. 15, «Наука», 1965, 245 — 248. Белецкий М. И. Модель языка алгоритма грамматического анализа. — Сб. «Тезисы Конференции по обработке информации, машинному переводу и автоматическому чтению текста», ВИНИТИ, 1961, 12.
Белецкий М. И. Бесконтекстные и доминационные грамматики и связанные с ними алгоритмические проблемы. — Кибернетика, 1967, № 4, 90 — 97. Белецкий М. И., Григорян В. М., Заславский И. Д. Аксиоматическое описание порядка и управления слов в некоторых типах предложений. — Сб. «Математические вопросы кибернетики и вычислительной техники», № 1, Ереван, 1963, 71 — 85. Борщев В. Б., Хомяков М. В. Окрестностные грамматики и модели перевода. Часть 1.
Окрестностиые грамматики. — Научнотехническая информация, сер. 2, 1970, № 3, 39 — 44. Гл а дк ий А В, Конфигурационные характеристики языков.— Сб. «Проблемы кибернетики», вып. 10, Физматгиз, 1963(а), 251 — 260. Г л а дк и й А. В. О распознавании замещаемости в рекурсивных языках. — Алгебра и логика, 1963 (б), 2, № 3, 5 — 22. Гладкий А.
В. Грамматики с линеййой памятью.— Алгебра и логика, 1963(в), 2, № 5, 43 — 55. Гладкий А. В. Алгоритм распознавания конфигураций для класса автоматных языков.— Сб. «Проблемы кибернетики», вып. 12, «Наука», 1964(а), 243 — 245. Г л а д к и й А. В. Алгоритмическая природа инвариантных свойств грамматик непосредственно составляющих. — Алгебра и логика, 1964(б), 3, № 2, 17 — 32. Г л а дк и й А. В. О сложности вывода в грамматиках непосредственно составляющих.
— Алгебра и логика, 1964(в), 3, № 5 — 6, 29 — 44. Г л а д к и й А. В. Некоторые алрбритмические проблемы для КС- грамматик. — Алгебра и логика, 19%(а), 4, № 1, 3 — 13, Г л а д к и й А. В. Алгоритмическая нераспознаваемость сущест. венной неопределенности КС.языков. — Алгебра и логика, 1965(б), 4, № 4, 53 — 64. Гладкий А. В.
Лекции по математической лингвистике для студентов НГУ, изд. Йовосибирского гос. университета, 1966. Г л ад к и й А. В. Об описании синтаксической структуры предложения. — Сошрц!айопа( Бп2шз1(сз, УП. Вцбарез1, 1969, 21 — 44. ЛИТЕРАТУРА 350 ЛИТЕРАТУРА 351 Гладкий А. В. Описание синтаксической структуры предложения с помощью систем синтаксических групп. 1. Формальный аппарат. — Научно-техннческая информация, сер. 2, 1971, № 9, 35 — 38. Гладкий А. В., Дико вский А. Я. Теория формальных грамматик.— Труды 2-й Всесоюзной конференции по программированию, Приглашенные доклады (1-й вып.), Новосибирск, 1970, 43 — 70. Г л а д к и й А.
В,, М ельч у к И. А. Элементы математической лингвистики, «Наука», 1969. Гладкий А. В., Мельчук И. А. Грамматики деревьев. 1. Опыт формализации преобразований синтаксических структур естественного языка. — Сб. «Информационные вопросы семиотики, лингвистики н автоматического перевода», вып. 1, 1971, 16 — 41. Д и ко в с кн й А. Я. О соотношении между классом всех контекстно-свободных языков и классом детерминированных контекстно- свободных языков. — Алгебра и логика, 1969, 8, № 1, 44 — 64. Д и к о в с к и й А.
Я. Замечание о детерминированных линейных языках. — Сб. «Проблемы кибернетики», вып, 23, «Наука», 1970, 28!в 286. Дико вский А. Я. Густота — 'мера сложности вывода в контекстно-свободной грамматике. — Проблемы передачи информации, 19?2(а), 8, вып. 2, 92 — 105. Днко вский А. Я. Густота дерева вывода и активная емкость грамматики. — Проблемы передачи информации, 1972(б), 8, вып. 4. Ди ковский А. Я., Модин а Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
