Конус (формальные языки) - Cone (formal languages)
В формальная теория языка, а конус это набор формальные языки что есть некоторые желанные закрытие свойства, которыми обладают некоторые известные наборы языков, в частности, семейства обычные языки, контекстно-свободные языки и рекурсивно перечислимые языки.[1] Концепция конуса - более абстрактное понятие, которое включает все эти семейства. Аналогичное понятие верный конус, имея несколько расслабленные условия. Например, контекстно-зависимые языки не образуют конуса, но все же обладают необходимыми свойствами для формирования точного конуса.
Терминология конус имеет французское происхождение. В американской ориентированной литературе обычно говорят о полное трио. В трио соответствует верному конусу.
Определение
Конус - это семья языков, таких что содержит хотя бы один непустой язык, и для любого над некоторым алфавитом ,
- если это гомоморфизм от некоторым , язык в ;
- если является гомоморфизмом некоторого к , язык в ;
- если какой-либо регулярный язык больше , тогда в .
Семейство всех регулярных языков содержится в любом конусе.
Если ограничить определение гомоморфизмами, которые не вводят пустое слово тогда говорят о верный конус; обратные гомоморфизмы не ограничены. В рамках Иерархия Хомского, обычные языки, контекстно-свободные языки и рекурсивно перечислимые языки все являются конусами, тогда как контекстно-зависимые языки и рекурсивные языки - только точные конусы.
Отношение к преобразователям
А конечный преобразователь - конечный автомат, имеющий как вход, так и выход. Он определяет трансдукцию , отображение языка над входным алфавитом на другой язык над выходным алфавитом. Каждая из операций конуса (гомоморфизм, обратный гомоморфизм, пересечение с регулярным языком) может быть реализована с помощью преобразователя конечного состояния. И, поскольку преобразователи с конечным числом состояний закрыты относительно композиции, каждая последовательность операций конуса может выполняться преобразователем с конечным числом состояний.
И наоборот, каждое преобразование конечного состояния можно разложить на операции конуса. На самом деле для этого разложения существует нормальная форма:[2] который широко известен как Теорема Нивата:[3]А именно каждый такой можно эффективно разложить как, где гомоморфизмы, а является обычным языком и зависит только от .
В целом это означает, что семейство языков является конусом тогда и только тогда, когда оно замкнуто относительно преобразований конечного состояния. Это очень мощный набор операций. Например, легко написать (недетерминированный) преобразователь конечного состояния с алфавитом что удаляет каждую секунду в словах четной длины (и не меняет слов в противном случае). Поскольку контекстно-свободные языки образуют конус, они закрываются при этой экзотической операции.
Смотрите также
Заметки
использованная литература
- Гинзбург, Сеймур; Грейбах, Шейла (1967). «Абстрактные семейства языков». Протокол конференции 1967 г. восьмого ежегодного симпозиума по теории коммутации и автоматов, 18–20 октября 1967 г., Остин, Техас, США. IEEE. С. 128–139.
- Ниват, Морис (1968). "Transductions des langages de Chomsky". Annales de l'Institut Fourier. 18 (1): 339–455. Дои:10.5802 / aif.287.
- Сеймур Гинзбург, Алгебраические и теоретико-автоматные свойства формальных языков, Северная Голландия, 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.
внешние ссылки
- Энциклопедия математики: Трио, Springer.