Абстрактная семья языков

• Определение абстрактного семейства языков

  • Абстрактное семейство языков обобщает характеристики обычных, контекстно-свободных и рекурсивно перечислимых языков. 

• Формальное определение языка

  • Язык L является подмножеством Σ∗, где Σ — набор абстрактных символов. 

• Определение семейства языков

  • Семейство языков — это упорядоченная пара (Σ, Λ), где Σ — бесконечный набор символов, а Λ — набор формальных языков. 
  • Для каждого языка L в Λ существует подмножество Σ1, такое, что L ⊆ Σ1∗. 
  • В семействе языков есть языки, которые не содержат пустое слово, обратные гомоморфизмы и пересечения с обычным языком. 

• Трио и полное трио

  • Трио — это семейство языков, замкнутое по гомоморфизмам. 
  • Полное трио — это трио, замкнутое относительно произвольного гомоморфизма. 

• Примеры семейств языков

  • Обычные языки, контекстно-свободные языки и рекурсивно перечислимые языки являются полными AFL. 
  • Контекстно-зависимые и рекурсивные языки являются AFL, но не полными AFL. 

• Происхождение теории AFL

  • Сеймур Гинзбург и Шейла Грейбах представили первую статью по теории AFL в 1967 году. 

• Библиография

  • Ссылки на книги Сеймура Гинзбурга и Джона Э. Хопкрофта и Джеффри Д. Ульмана, которые содержат информацию о свойствах замыкания семейств языков.