Введение в теорию формальных языков

Введение в теорию формальных языков
Е.И. Бунина, А.Ю. Голубков
  • Год:
    2006
  • Тип издания:
    Учебное пособие
  • Объем:
    96 стр. / 5.46 п.л
  • Формат:
    60x84/16
  • ISBN:
    5-7038-2880-5
  • Читать Online

Ключевые слова: гомоморфизмы, иерархия Хомского, конечные автоматы, контекстно-свободные языки, машины Тьюринга, порождающие грамматики, распознаватели, регулярные множества, формальные грамматики, формальные языки

Пособие содержит теоретические сведения по курсу "Теория формальных языков". Особое внимание уделено связи формальных грамматик в иерархии Хомского с соответствующими распознающими устройствами.

Для студентов 3-4-го курсов компьютерных, математических и лингвистических специальностей.

ОГЛАВЛЕНИЕ
Глава 1. Основные понятия и определения
1.1. Формальные языки
1.2. Гомоморфизмы
1.3. Порождающие грамматики
1.4. Примеры грамматик и задачи на построение грамматик
1.5. Иерархия грамматик Хомского
1.6. Распознаватели
Глава 2. Конечные автоматы, регулярные выражения, праволинейные грамматики
2.1. Регулярные множества и регулярные выражения
2.2. Регулярные множества и праволинейные грамматики
2.3. Конечные автоматы
2.4. Конечные автоматы и регулярные множества
2.5. Свойства регулярных множеств
2.6. Свойства замкнутости регулярных множеств
2.7. Проблемы разрешимости, связанные с регулярными множествами
2.8. Задачи
Глава 3. Контекстно-свободные языки
3.1. Деревья выводов
3.2. Преобразования КС-грамматик
3.3. Нормальная форма Хомского
3.4. Задачи
3.5. Автоматы с магазинной памятью
3.6. Связь между МП-автоматами и КС-грамматиками
3.7. Детерминированные МП-автоматы
3.8. Задачи
3.9. Лемма о разрастании для КС-языков
3.10. Свойства замкнутости КС-языков
3.11. Проблемы разрешимости для КС-грамматик
Глава 4. Порождающие грамматики и машины Тьюринга
4.1. Нормальная форма порождающей грамматики
4.2. Машины Тьюринга
4.3. Теоремы о совпадении
4.4. Контекстно-зависимые грамматики и линейно-ограниченные машины Тьюринга

Авторы работы: Бунина Е.И., Голубков А.Ю.