Конус (формальные языки)

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

Терминологический конус имеет французское происхождение. В американской литературе обычно говорят о полном трио . Трио . соответствует верному конусу

Определение

Конус – это семья ${\mathcal {S}}$ языков таких, что ${\mathcal {S}}$ содержит хотя бы один непустой язык, и для любого $L\in {\mathcal {S}}$ над каким-то алфавитом $\Sigma$,

• если $h$ является гомоморфизмом из $\Sigma ^{\ast }$ некоторым $\Delta ^{\ast }$, язык $h(L)$ находится в ${\mathcal {S}}$;
• если $h$ является гомоморфизмом некоторого $\Delta ^{\ast }$ к $\Sigma ^{\ast }$, язык $h^{-1}(L)$ находится в ${\mathcal {S}}$;
• если $R$ любой обычный язык поверх $\Sigma$, затем $L\cap R$ находится в ${\mathcal {S}}$.

Семейство всех регулярных языков содержится в любом конусе.

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

с

Конечный преобразователь — это конечный автомат, который имеет как вход, так и выход. Он определяет трансдукцию $T$, отображение языка $L$ поверх входного алфавита на другой язык $T(L)$ над выходным алфавитом. Каждую из конусных операций (гомоморфизм, обратный гомоморфизм, пересечение с регулярным языком) можно реализовать с помощью преобразователя конечных состояний. А поскольку преобразователи с конечным состоянием замкнуты относительно композиции, каждая последовательность конусных операций может быть выполнена преобразователем с конечным состоянием.

И наоборот, каждое преобразование конечного состояния $T$ можно разложить на конусные операции. Фактически, существует нормальная форма этого разложения: которая широко известна как теорема Нивата : А именно, каждый такой $T$ можно эффективно разложить как $T(L)=g(h^{-1}(L)\cap R)$, где $g,h$ являются гомоморфизмами, а $R$ является регулярным языком, зависящим только от $T$.

В целом это означает, что семейство языков является конусом тогда и только тогда, когда оно замкнуто относительно преобразований конечных состояний. Это очень мощный набор операций. Например, легко написать (недетерминированный) преобразователь конечных состояний с алфавитом $\{a,b\}$ это удаляет каждую секунду $b$ в словах четной длины (и в противном случае не меняет слова). Поскольку контекстно-свободные языки образуют конус, они замыкаются при этой экзотической операции.

См. также

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

Ссылки

• Гинзбург, Сеймур; Грейбах, Шейла (1967). «Абстрактные семьи языков». Отчет конференции 1967 г. Восьмого ежегодного симпозиума по теории коммутации и автоматов, 18–20 октября 1967 г., Остин, Техас, США . IEEE. стр. 128–139.

• Ниват, Морис (1968). «Переводы языков Хомского» . Анналы Института Фурье . 18 (1): 339–455. дои : 10.5802/aif.287 .
• Сеймур Гинзбург , Алгебраические и теоретико-автоматные свойства формальных языков , Северная Голландия, 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 .

Внешние ссылки

• Энциклопедия математики: Трио , Спрингер.