Оглавление
Абстрактная семья языков
-
Определение абстрактного семейства языков
- Абстрактное семейство языков обобщает характеристики обычных, контекстно-свободных и рекурсивно перечислимых языков.
-
Формальное определение языка
- Язык L является подмножеством Σ∗, где Σ – набор абстрактных символов.
-
Определение семейства языков
- Семейство языков – это упорядоченная пара (Σ, Λ), где Σ – бесконечный набор символов, а Λ – набор формальных языков.
- Для каждого языка L в Λ существует подмножество Σ1, такое, что L ⊆ Σ1∗.
- В семействе языков есть языки, которые не содержат пустое слово, обратные гомоморфизмы и пересечения с обычным языком.
-
Трио и полное трио
- Трио – это семейство языков, замкнутое по гомоморфизмам.
- Полное трио – это трио, замкнутое относительно произвольного гомоморфизма.
-
Примеры семейств языков
- Обычные языки, контекстно-свободные языки и рекурсивно перечислимые языки являются полными AFL.
- Контекстно-зависимые и рекурсивные языки являются AFL, но не полными AFL.
-
Происхождение теории AFL
- Сеймур Гинзбург и Шейла Грейбах представили первую статью по теории AFL в 1967 году.
-
Библиография
- Ссылки на книги Сеймура Гинзбурга и Джона Э. Хопкрофта и Джеффри Д. Ульмана, которые содержат информацию о свойствах замыкания семейств языков.
Полный текст статьи: