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

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

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

Формальный язык — это множество L , для которого существует конечный набор абстрактных символов Σ такой, что , где * — операция звезды Клини . ${\displaystyle L\subseteq \Sigma ^{*}}$

Семья языков – это упорядоченная пара , где ${\displaystyle (\Sigma ,\Lambda )}$

1. Σ — бесконечный набор символов;
2. Λ — множество формальных языков;
3. Для каждого L в Λ существует конечное подмножество такое, что ; и ${\displaystyle \Sigma _{1}\subseteq \Sigma }$ ${\displaystyle L\subseteq \Sigma _{1}^{*}}$
4. L ≠ Ø для некоторого L из Λ .

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

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

( Полный ) полу-АФЛ — это (полное) трио, замкнутое относительно союза .

(Полный) AFL — это (полный) полу-AFL, замкнутый относительно конкатенации и операции Клини плюс .

Некоторые семьи языков

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

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

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

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

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

Примечания

1. Матееску, А.; Саломаа, А. (2001) [1994], «Абстрактная семья языков», Энциклопедия математики , EMS Press
2. Паун, Гх. (2001) [1994], «Операции АФЛ», Энциклопедия математики , EMS Press
3. Гинзбург и Грейбах (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: Слово, язык, грамматика . Спрингер-Верлаг. стр. 175–252. ISBN 3-540-61486-9.