Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 125

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 119 120 121 122 123 124 < 125 > 126 127 128 129 130 131 .. 136 >> Следующая

1963(b)], Теорема 2.2 принадлежит Р. Буку [Book 1969]. Теоремы 2.4
и 2.5 — это известные теоремы Г. С. Цейтина (см. [Яновская 1959, стр. 45, Трахтенброт 1967, стр. 152]) и М. Рабина [Rabin 1959 ***), Трахтенброт 1967, стр. 194] из теории сложности вычислений, пере-
*) Эта работа содержит неточности в определениях, впоследствии замеченные и исправленные К. Чуликом [Culik 1965].
**) В русском переводе этой книги — «полусистема Туэ» (стр. 340).
***) В этой работе нет доказательства.
344
БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
несенные на случай грамматик. Приводимые нами доказательства этих теорем по существу заимствованы из книги [Трахтенброт 1967]. Изучению временной сложности грамматик посвящена книга [Book 1969].
К главе 3.
Понятие дерева вывода восходит к основополагающим работам Н. Хомского [Chomsky 1956, 1957, 1959(a), 1963]. Ему же принадлежат понятие неукорачивающей грамматики и теорема 3.1 [Chomsky 1959(a)]. Теорема 3.2, в несколько иной форме, доказана в [Kuroda 1964]. Другое доказательство существования для всякой грамматики без растяжения эквивалентной ей НС-грамматики (положенное в основу доказательства теоремы 3 5) было дано в [Гладкий 1963(b)], Теорема 3.3 отмечена в [Гладкий 1966]. (Эффективная) замкнутость класса НС-языков относительно пересечения доказана независимо в трех работах [Landweber 1963, Гладкий 1963(b), Kuroda 1964]. Теорема 3.7 доказана в [Гладкий 1964(b)], Использованная в ее доказательстве техника следов независимо разработана — применительно к детерминированным машинам Тьюринга — Б. А. Трахтен-бротом [Трахтенброт 1964], Я. М. Барздинем [Барздинь 1965], М. Ра-бином [Rabin 1963], Ф. Хенни [Hennie 1965]. Лемма 3.2 принадлежит фактически Б. А. Трахтенброту [Трахтенброт 1964]. Пример, аналогичный примеру 1 из § 3.4, был впервые построен Р. Парикхом [Parikh 1961]. Примеры односторонних НС-грамматик, выводящих за пределы класса Б-языков, были указаны независимо Л. Хейнсом [Haines 1965]*), Л. Г. Самойленко [Самойленко 1968] и И. Гавелом [Havel 1969]. Теорема 3.8 доказана Л. Хейнсом [Haines 1969, 1970].
К главе 4.
Основные факты теории Б-языков были впервые систематизированы— и многие из них впервые получены — в статье' [Ваг-Hillel — Perles—Sfiamir 1961]. В ней содержится практически все изложенное в §§ 4.1, 4.2, а также теорема 4.5 (и некоторые другие результаты, которые будут отмечены ниже). Большую роль в развитии теории Б-языков сыграла работа Р. Парикха [Parikh
1961]**), в которой введено понятие однозначности языка и указан первый пример неоднозначного бесконтекстного языка (пример 3 из § 4.4); там же доказана теорема 4.6. Теорема 4.7 доказана в [Гладкий 1965(6)]. Теорема 4.8 впервые опубликована, видимо, в [Schein-berg I960]; она имеется также в [Bar-Hillel — Perles — Shamir 1961]. Неоднозначность Б-языков изучалась в [Ginsburg — Ullian 1966], где для важного в приложениях случая ограниченных языков (см. упражнение 5.32) получено необходимое и достаточное условие неоднозначности (соответствующие результаты изложены также в [Ginsburg
1966, гл. 6]). Понятие МП-машины введено Н. Хомским [Chomsky
*) О существовании примера, построенного в диссертации [Haines 1965], автору стало известно из рукописи [Haines 1970], любезно присланной ему Л. Хейнсом в конце 1970 г.
**) Преприпт, впоследствии перепечатанный в [Parikh 1966],
БИБЛИОГРАФИЧЕСКИЕ -ЗАМЕЧАНИЯ
345
1962]*); им же доказана теорема 4.9 [Chomsky 1962, 1963]. Впоследствии эта теорема несколько раз передоказывалась, в частности Р. Эви [Evey 1963] и Г. С. Цейтиным (не опубликовано). Конструкции, используемые для ее доказательства в настоящей книге (леммы 4.12—4.14), навеяны идеями Ю. А. Шрейдера, В. Б. Борщева и М. В. Хомякова [Шрейдер 1969, Борщев — Хомяков 1970] и JI. С. Мо-диной [Модина 1970]. Детерминированные МП-машины впервые рассмотрел М. Шютценберже [Schiitzenberger 1963]; они изучались также
С. Гинзбургом и Ш. Грейбах [Ginsburg — Greibach 1966(6)] и А. Я . Диковским [Диковский 1969]. Теория Б-языков посвящена книга [Ginsburg 1966].
К главе 5.
Конечные автоматы в явной форме подвергаются систематическому изучению с 50-х гг. (их называют также «последовательностными машинами», «автоматами Мура-Мили»); однако в не-
• явном виде они рассматривались и раньше в теории алгоритмов (головка машины Тьюринга по существу представляет собой конечный автомат; см. [Turing 1936—1937]) и в теории информации (см., например, [Shannon 1948]**)). Теорема 5.3 в неявном, виде установлена Ю. Т. Медведевым [Медведев 1956]; в явной форме впервые опубликована в [Rabin — Scott 1959]. Регулярные языки введены в [Юеепе 1956]; там же отмечена (эффективная) замкнутость класса регулярных языков относительно основных операций и доказана теорема, по существу совпадающая с теоремой 5.6. Теорема 5.7 впервые появилась, по-видимому, в [Myhill 1957] и [Nerode 1958]. Изучению ОА-граммагик посвящена работа [Chomsky — Miller 1958]. Линейные грамматики введены в [Schiitzenberger 1961], металинейные — либо в той же работе ***), либо в [Chomsky 1963] и [Chomsky— Schiitzenber-ger 1963]. МП-машины с ограниченным числом поворотов и ОАЕВ-грамматики изучались в [Ginsburg — Spanier 1966]; в этой работе доказаны теоремы 5.11 и 5.12.
Предыдущая << 1 .. 119 120 121 122 123 124 < 125 > 126 127 128 129 130 131 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed