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

Abstract family of languages

В Информатика, в частности в области формальный язык теория, абстрактная семья языков абстрактное математическое понятие, обобщающее характеристики, общие для обычные языки, то контекстно-свободные языки и рекурсивно перечислимые языки, и другие семейства формальных языков, изучаемые в научной литературе.

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

А формальный язык это набор L для которого существует конечный набор абстрактных символов Σ такой, что , где Клини звезда операция.

А семья языков упорядоченная пара , куда

  1. Σ бесконечный набор символов;
  2. Λ набор формальных языков;
  3. Для каждого L в Λ существует конечное подмножество такой, что ; и
  4. L ≠ Ø для некоторых L в Λ.

А трио это семья языков закрыто под е-свободный гомоморфизм, обратный гомоморфизм, и пересечение с обычным языком.

А полное трио, также называется конус, является трио, замкнутым относительно произвольного гомоморфизма.

А (полный) полу-AFL (полное) трио, замкнутое под союз.

А (полный) AFL это (полный) полу-AFL закрыт под конкатенация и Клини плюс.

Некоторые семейства языков

Ниже приведены некоторые простые результаты изучения абстрактных семейств языков.[1][2]

В рамках Иерархия Хомского, обычные языки, контекстно-свободные языки и рекурсивно перечисляемые языки - все это полные AFL. Тем не менее контекстно-зависимые языки и рекурсивные языки являются AFL, но не полными AFL, поскольку они не замкнуты относительно произвольных гомоморфизмов.

Семейство обычных языков содержится в любом конусе (полное трио). Другие категории абстрактных семейств можно идентифицировать путем закрытия при выполнении других операций, таких как перемешивание, обращение или замена.[3]

Происхождение

Сеймур Гинзбург из Университет Южной Калифорнии и Шейла Грейбах из Гарвардский университет представил первую теоретическую работу AFL на восьмой ежегодной конференции IEEE Симпозиум по теории переключений и автоматов в 1967 г.[4]

Примечания

  1. ^ Гинзбург (1975)
  2. ^ Mateescu, A .; Саломаа, А. (2001) [1994], «Абстрактная семья языков», Энциклопедия математики, EMS Press
  3. ^ Păun, Gh. (2001) [1994], «Операции ВСЛ», Энциклопедия математики, EMS Press
  4. ^ Гинзбург и Грейбах (1967)

Рекомендации

  • Гинзбург, Сеймур; Грейбах, Шейла (1967). «Абстрактные семейства языков». Протокол конференции 1967 г. восьмого ежегодного симпозиума по теории коммутации и автоматов, 18–20 октября 1967 г., Остин, Техас, США. IEEE. С. 128–139.
  • Сеймур Гинзбург, Алгебраические и теоретико-автоматные свойства формальных языков, Северная Голландия, 1975 г., ISBN 0-7204-2506-9.
  • Джон Э. Хопкрофт и Джеффри Д. Уллман, Введение в теорию автоматов, языки и вычисления, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. Глава 11: Замыкающие свойства семейств языков.
  • Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты теории классического языка». В Розенберге, Гжегоже; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика. Springer-Verlag. С. 175–252. ISBN 3-540-61486-9.