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

В формальная теория языка, а конус это набор формальные языки что есть некоторые желанные закрытие свойства, которыми обладают некоторые известные наборы языков, в частности, семейства обычные языки, контекстно-свободные языки и рекурсивно перечислимые языки.[1] Концепция конуса - более абстрактное понятие, которое включает все эти семейства. Аналогичное понятие верный конус, имея несколько расслабленные условия. Например, контекстно-зависимые языки не образуют конуса, но все же обладают необходимыми свойствами для формирования точного конуса.

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

Определение

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

  • если это гомоморфизм от некоторым , язык в ;
  • если является гомоморфизмом некоторого к , язык в ;
  • если какой-либо регулярный язык больше , тогда в .

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

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

Отношение к преобразователям

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

И наоборот, каждое преобразование конечного состояния можно разложить на операции конуса. На самом деле для этого разложения существует нормальная форма:[2] который широко известен как Теорема Нивата:[3]А именно каждый такой можно эффективно разложить как, где гомоморфизмы, а является обычным языком и зависит только от .

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

Смотрите также

Заметки

использованная литература

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

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