Теория формальных языков, Пентус А.Е., Пентус М.Р., 2004

Теория формальных языков, Пентус А.Е., Пентус М.Р., 2004.

   Учебное пособие посвящено классическому разделу математической лингвистикой и теоретической информатики — теории формальных языков. Рассматриваются порождающие грамматики, классификация формальных языков по Хомскому, регулярные выражения, конечные автоматы, автоматы с магазинной памятью, алгоритмические проблемы, связанные с контекстно-свободными грамматиками.
Для студентов, аспирантов и специалистов, занимающихся математической лингвистикой или теоретической информатикой.




Теорема Клини.
Определение 5.11. Назовём обобщённым конечным автоматом аналог конечного автомата, где переходы помечены не словами, а регулярными выражениями. Метка пути такого автомата — произведение регулярных выражений на переходах данного пути. Слово w допускается обобщённым конечным автоматом, если оно принадлежит языку, задаваемому меткой некоторого успешного пути.

Замечание 5.12. Каждый конечный автомат можно преобразовать в обобщённый конечный автомат, допускающий те же слова. Для этого достаточно заменить всюду в метках переходов пустое слово на 1, а каждое непустое слово на произведение его букв.

Замечание 5.13. Если к обобщённому конечному автомату добавить переход с меткой 0, то множество допускаемых этим автоматом слов не изменится.

ОГЛАВЛЕНИЕ.
1. Слова, языки и грамматики.
1.1. Формальные языки.
1.2. Гомоморфизмы.
1.3. Порождающие грамматики.
1.4. Классы грамматик.
2. Конечные автоматы.
2.1. Недетерминированные конечные автоматы.
2.2*. Конфигурации конечного автомата.
2.3. Конечные автоматы с однобуквенными переходами.
2.4. Характеризация праволинейных языков.
2.5*. Нормальная форма праволинейных грамматик.
2.6. Детерминированные конечные автоматы.
3. Основные свойства автоматных языков.
3.1. Свойства замкнутости класса автоматных языков.
3.2. Пересечение и дополнение автоматных языков.
3.3. Лемма о разрастании для автоматных языков.
3.4. Примеры неавтоматных языков.
4. Дополнительные свойства автоматных языков.
4.1. Гомоморфизмы и автоматные языки.
4.2*. Длины слов в автоматных языках.
5. Регулярные выражения.
5.1. Определение регулярного выражения.
5.2*. Свойства регулярных выражений.
5.3. Теорема Клини.
6. Синтаксические моноиды.
6.1. Множества правых контекстов.
6.2. Минимизация детерминированных конечных автоматов.
6.3. Множества двусторонних контекстов.
7. Неоднозначность в контекстно-свободных грамматиках.
7.1. Деревья вывода.
7.2. Однозначные контекстно-свободные грамматики.
7.3*. Однозначные праволинейные грамматики.
7.4. Языки Дика и Лукасевича.
8. Нормальные формы контекстно-свободных грамматик.
8.1. Устранение бесполезных символов.
8.2. Устранение е-правил.
8.3. Нормальная форма Хомского.
8.4*. Нормальная форма Грейбах.
9. Основные свойства контекстно-свободных языков.
9.1. Лемма о разрастании для контекстно-свободных языков.
9.2. Свойства замкнутости класса линейных языков.
9.3. Свойства замкнутости класса контекстно-свободных языков.
9.4. Пересечение и дополнение контекстно-свободных языков.
9.5. Пересечение контекстно-свободного языка с автоматным языком.
9.6*. Теорема Парика.
10. Автоматы с магазинной памятью.
10.1. Определение автомата с магазинной памятью.
10.2. Характеризация контекстно-свободных языков.
10.3*. Автоматы с магазинной памятью с однобуквенными переходами.
11. Дополнительные свойства контекстно-свободных языков.
11.1*. Деление контекстно-свободных языков.
11.2. Гомоморфизмы и контекстно-свободные языки.
11.3*. Представления контекстно-свободных языков посредством гомоморфизмов.
12. Детерминированные контекстно-свободные языки.
12.1. Детерминированные автоматы с магазинной памятью.
12.2*. Свойства класса детерминированных контекстно-свободных языков.
13. Алгоритмические проблемы.
13.1. Машины Тьюринга.
13.2. Массовые задачи.
13.3*. Грамматики типа 0.
13.4. Проблема соответствий Поста.
14. Алгоритмически разрешимые проблемы.
14.1. Неукорачивающие грамматики.
14.2*. Линейно ограниченные автоматы.
14.3. Проблема выводимости слова.
14.4. Проблема пустоты языка.
14.5. Проблема бесконечности языка.
14.6. Проблема равенства автоматных языков.
15. Алгоритмически неразрешимые проблемы.
15.1. Пересечение контекстно-свободных языков.
15.2. Проблема однозначности.
15.3. Дополнение контекстно-свободного языка.
15.4. Проблема автоматности.
15.5. Проблемы контекстно-свободности.
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория формальных языков, Пентус А.Е., Пентус М.Р., 2004 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Пентус :: теорема Клини