|
СОДЕРЖАНИЕ
Предисловие редакторов перевода............... 5 I. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Дональд Кнут. О переводе (трансляции) языков слева направо. Перевод А. А. Мучника....................... 9 Дэниел Леман. LR (k)-грамматики и детерминированные языки. Перевод А. А. Мучника......................43 Джен Эрли. Эффективный алгоритм анализа контекстно-свободных языков. Перевод А. А. Мучника................47 А. Кореняк, Дж. Хопкрофт. Простые детерминированные языки. Перевод А. Л. Фуксмана...................71 Эдвард Ашкрофт, Зохар Манна, Амир Пнуели. Разрешимые свойства од-ноаргументных функциональных схем. Перевод А. Н Маслова... 97 Уильям Огден. Результат, полезный для доказательства существенной неоднозначности. Перевод М. В. Ломковской......... 109 Джон Хопкрофт. О проблемах эквивалентности и включения для бесконтекстных языков. Перевод М. В. Ломковской.........114 Шейла Грейбах. О неразрешимых свойствах формальных языков. Перевод А. Л. Семенова...................123 II. РАСШИРЕНИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Альфред Ахо. Индексные грамматики — расширение контекстно-свободных грамматик. Перевод В. А. Козмидиади............ 130 Шейла Грейбах, Джон Хопкрофт. Грамматики с рассеянным контекстом. Перевод Э. Д. Стойкого..................166 А. Ахо, Дж. Хопкрофт, Дж. Улман. Временная и ленточная сложности языков, допускаемых магазинными автоматами. Перевод А. А. Мучника........................185 К. Чулик, II, Ч. Дж. Морей. Формальные схемы переводов. Перевод Е. С. Бургиной..................... 198 III. АКСИОМАТИЧЕСКИ ОПРЕДЕЛЯЕМЫЕ СЕМЕЙСТВА ЯЗЫКОВ Сеймур Гинзбург, Шейла Грейбах. Абстрактные семейства языков. Перевод А. Я. Диковского.............233 Сеймур Гинзбург, Шейла Грейбах. Главные абстрактные семейства языков. Перевод М. В. Ломковской..............282 Сеймур Гинзбург, Джин Роуз. Об однопорождаемости некоторых абстрактных семейств языков. Перевод А. Я. Диковского.... 321 Дж. Уллиэн. Три теоремы о главных абстрактных семействах языков. Перевод А- Я. Диковского.................341 |