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

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

Формальные определения [ править ]

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

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

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

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

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

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

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

Некоторые семьи языков [ править ]

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

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

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

Происхождение [ править ]

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

Примечания [ править ]

^ Матееску, А.; Саломаа, А. (2001) [1994], «Абстрактное семейство языков» , Энциклопедия математики , EMS Press
^ Паун, Г. (2001) [1994], «Операции AFL» , Математическая энциклопедия , EMS Press
^ Гинзбург и Грейбах (1967)

Ссылки [ править ]

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

[SpringerAFL-1] Матееску, А.; Саломаа, А. (2001) [1994], «Абстрактное семейство языков» , Энциклопедия математики , EMS Press

[SpringerOps-2] Паун, Г. (2001) [1994], «Операции AFL» , Математическая энциклопедия , EMS Press

[3] Гинзбург и Грейбах (1967)

[1]

[2]

[3]