Теория формальных грамматик, Гросс М., Лантен А, 1971
Теория формальных грамматик, Гросс М., Лантен А, 1971.
Фрагмент из книги.
«Универсальный» метод решения проблемы эквивалентности, который прежде всего приходит в голову, состоит в следующем: взяв произвольную пару слов S и Г, последовательно образовать все слова, смежные с S, потом все слова, смежные с каждым из слов, полученных на первом шаге, и т. д., т. е., короче говоря, перечислить все слова, эквивалентные слову S, применяя сначала одно, потом два, потом три преобразования и т. д., пока мы не дойдем до Т. Однако сколько бы преобразований ни было выполнено, тот факт, что Т не найдено, еще ничего не означает: оно может быть получено после очередных преобразований. Таким образом, наш наивный «универсальный» метод не гарантирует нахождения решения.
Возникает вопрос: существует ли настоящий универсальный метод, позволяющий решать проблему эквивалентности слов? После того как мы уточним представление о методе решения вообще — точнее, введем понятие алгоритма, —можно будет показать, что ответ на этот вопрос является отрицательным.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода.
От авторов.
Предисловие.
ЧАСТЬ I ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ЛОГИКИ И АЛГЕБРЫ
Глава I. Слова (цепочки). Полугруппы. Языки.
§ 1.1. Свободная полугруппа.
§ 1.2. Операции над словами.
§ 1.3. Языки.
§ 1.4. Упражнения.
Глава //. Общие сведения о формальных системах.
§ 2.1. Описание исчисления высказываний на интуитивном уровне
§ 2.2. Понятие формальной системы.
§ 2.3. Формализованный вариант исчисления высказываний.
§ 2.4. Определение формальной системы.
Глава ///. Комбинаторные системы.
§ 3.1. Определение комбинаторных систем.
§ 3.2. Нормальные системы.
§ 33 Упражнения.
§ 3.4. Независимость от алфавита.
Глава IV. Алгоритмы. Машины Тьюринга.
§ 4.1. Алгоритмы.
§ 4.2. Машины Тьюринга.
§ 4.3. «Численные» машины Тьюринга.
§ 4.4. Упражнения.
Глава V Вычислимость и разрешимость.
§ 5 1 Исчисление функций.
§ 5.2 Операции над функциями.
§ 5.3. Метод Гёделя.
§ 5.4. Рекурсивные и рекурсивно перечислимые множества.
§ 5.5 Замечания и дополнения.
Глава VI. Комбинаторные системы и машины Тьюринга: неразрешимые проблемы.
§ 6.1. Комбинаторные системы и машины Тьюринга.
5 6.2. Неразрешимые проблемы.
ЧАСТЬ И. НЕКОТОРЫЕ ЗАМЕЧАТЕЛЬНЫЕ КЛАССЫ ЯЗЫКОВ
Глава VII. Контекстно-свободные языки (языки Хомского). общая характеристика и основные свойства.
§ 7.1. Грамматика и описание синтаксических структур.
§ 7.2. Определения. Распознаваемые свойства.
§ 7 3. Свойства замкнутости.
§ 7.4. Специальные классы КС-языков.
§ 7.5. Упражнения.
Глава VIII. Нераспознаваемые свойства КС-грамматик.
§8 1. Проблемы, связанные с пересечением.
§ 8 2. Проблемы, связанные с неоднозначностью.
§ 8 3. Существенная неоднозначность минимальных линейных языков
Глава IX. Автоматы с магазинной памятью.
§ 9.1. Автоматы, допускающие языки.
§ 9.2. Автоматы, порождающие языки.
§ 9.3. Класс языков, допускаемых (порождаемых) МП-автоматами.
§ 9 4. Приложения КС-языков.
Глава X Автоматные языки и конечные автоматы.
§ 10 1. А-грамматики.
§ 10.2. Конечные автоматы.
§ 10.3. Некоторые обобщения и видоизменения конечных автоматов.
§ 10 4. Свойства замкнутости Представление А-языков по Клини.
§ 10 5. А-языки и КС-языки.
§ 106. Односторонние конечные преобразователи.
Глава XI. Задание языков с помощью систем уравнений.
§ 11.1. Функции, аргументами и значениями которых являются языки
§ 112. Языки и формальные степенные ряды.
Глава XI/. Грамматики непосредственно составляющих Автоматы с линейно
ограниченной памятью.
§ 12.1. Грамматики непосредственно составляющих (НС-грамматики)
§ 12.2. Линейно ограниченные автоматы.
§ 12.3 Классификация автоматов.
§ 12.4 Упражнения.
ЧАСТЬ 111. АЛГЕБРАИЧЕСКИЙ ПОДХОД
Глава XIII. Гомоморфизмы полугрупп.
§ 13.1. Произвольные полугруппы.
§ 132. Конгруэнция и эквивалентности, сопоставляемые языку.
§ 13.3. Понятия, связанные с кодами.;
Глава XIV. Дополнительные сведения об автоматных языках.
§ 14.1. Стандартные А-языки.
§ 14 2. Свойства стандартных А-языков.
§ 14.3. Алгебраическое описание А-языков.
§ 14.4. Преобразования.
Глава XV. Дополнительные сведения о КС-языках.
§ 15 1. Языки Дика.
§ 15.2. Стандартные КС-языки.
§ 15.3. Совпадение класса КС-языков с классом языков, допускаемых
автоматами с магазинной памятью.
§ 15.4 Упражнения.
Глава XV/. Алгебраические языки.
§ 16.1. Дополнительные сведения о формальных степенных рядах.
§ 162. Алгебраические ряды.
§ 16 3 Приложения к языкам.
§ 16.4. Упражнения.
§ 165. Применение «языковых» уравнений в комбинаторной геометрии
ПРИЛОЖЕНИЕ. ТРАНСФОРМАЦИОННЫЕ ГРАММАТИКИ
§ 1. Формальные грамматики и естественные языки.
§ 2. КС-грамматики и трансформации.
§ 3. Расширение грамматики.
§ 4. Проблемы, связанные с трансформациями.
Избранная библиография.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12759 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
#bty_languages@look_read
по по итальянскому языку1. Н.А. Рыжак Е.А. Рыжак Самоучитель итальянского языка для начинающих ( издание 2-е)2. Н.А. Рыжак Е.А. Рыжак Учебник итальянского языка (продвинутый этап обучения) Dall'italia . . .
-
#bty_languages@look_read
УЧЕБНИК ДЛЯ UPPER-INTERMEDIATE"NATURAL ENGLISH"(Сохраняем, делимся с друзьями!)Современный, сосредоточенный на развитии разговорных навыков общий английский курс, который помогает студентам использова . . .
-
#bty_books@look_read
OF THREE" (Ann Baker, Cambridge University) - отличный курс по произношению для Elementary. Идеально подойдет тем, кто хотел бы научиться правильному произношению начиная с азов. Все упражнения озвуче . . .
-
#bty_books@look_read
на английском с переводом на русский: наслаждайтесь книгами в оригинале и проверяйте себя по русскому параллельному тексту.1) Jonathan Livingston Seagull / Чайка по имени Джонатан Ливингстон - Richard . . .
-
#bty_languages@look_read
НА АНГЛИЙСКОМ ЯЗЫКЕ:1) Forrest Gump by Winston GroomИстория умственно отсталого юноши, рассказанная им самим на страницах этой книги, является воплощением мифа об «американской мечте» и одновременно о . . .
-
#bty_languages@look_read
НА АНГЛИЙСКОМ ЯЗЫКЕ.Для разных уровней (уровень указан в названии).1 -2) Beginner (Level 1)3) Elementary ( Level 2)4) Intermediate ( Level 4)5) Upper-Intermediate (Level 5) . . .
-
#bty_languages@look_read
WORD SKILLS - уникальный трёхуровневый тренажёр для увеличения словарного запаса.1) Oxford Word Skills Basic Book(для начинающих)2) Oxford Word Skills Intermediate3) Oxford Word Skills Advanced . . .
-
#bty_books@look_read
книг о Гарри Поттере. . . .
-
#bty_languages@look_read
for the Memoriesby Cecelia AhernHow can you know someone you’ve never met? Joyce Conway remembers things she shouldn’t. She knows about tiny cobbled streets in Paris, which she has never visited. And . . .
-
#bty_languages@look_read
книги для среднего - выше среднего уровня.1) The Notebook (Nicholas Sparks)2) The Great Gatsby (F. Scott Fitzgerald)3) Extremely Loud and Incredibly Close (Jonathan Safran Foer)4) Great Expectations ( . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Теория формальных грамматик, Гросс М., Лантен А, 1971. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.