Актуальность темы. Всюду в данной работе под словом «язык»
понимается формальный язык над конечным фиксированным алфавитом Σ, т.е. подмножество свободного моноида Σ∗ над Σ. Регулярные языки образуют важный класс формальных языков. Особенностью языков
этого класса является возможность компактного описания в различных
терминах (например, с помощью регулярных выражений, детерминированных автоматов, недетерминированных автоматов и др.). Разные
способы описания имеют разные области применения и разную степень
компактности, а изучение связи между различными способами составляет одно из наиболее активно развивающихся направлений в теории
сложности формальных систем. Отметим, что для некоторых важных
подклассов регулярных языков есть особые методы представления, которые учитывают специфику этих классов. Рассмотрим простой пример
одного из таких классов. Слово u ∈ Σ+ называется фактором слова w,
если w может быть представлено как w = xuy для некоторых x, y ∈ Σ∗.
Язык L ⊆ Σ∗ является факториальным, если L замкнут относительно
взятия факторов, т.е. для всякого w ∈ L все факторы w также принадлежат L. Любой факториальный язык можно описать с помощью
антисловаря, т.е. списка запрещенных факторов. Большую роль в теории и приложениях формальных языков играют факториальные языки
с конечным антисловарем (КАС-языки), см. [3]. Естественным объектом, описывающим КАС-язык, является антисловарь этого языка. Другой важный класс составляют идеальные языки. Напомним, что язык
I ⊆ Σ∗ называется двусторонним идеалом, если I непустой и Σ∗IΣ∗ ⊆ I.
Говоря «идеальный язык», или коротко «идеал», мы будем подразумевать, что рассматривается двусторонний идеальный язык. Понятие двустороннего идеала занимает центральное место в теории полугрупп [2].
Идеальные языки как двусторонние идеалы в свободном моноиде Σ∗ активно изучаются в связи с различными приложениями в компьютерных
науках на протяжении последних пятидесяти лет [6,10]. Нетрудно проверить, что язык L ⊆ Σ∗ является факториальным тогда и только тогда,
когда его дополнение Σ∗ L – идеал в Σ∗. Таким образом, факториальные языки суть в точности дополнения идеальных языков. Идеальные
языки возникают также в задачах, связанных с поиском подстроки в
строке [8]. Формально поиск в тексте w слова из L ⊆ Σ∗ эквивалентен
поиску факторов w, принадлежащих языку Σ∗LΣ∗, который является
двусторонним идеалом.
