Иерархии на обычных языках

Существует ли какая-либо известная «хорошая» иерархия $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (может быть конечной) внутри класса регулярных языков ? К счастью, классы в каждой иерархии отражают различную выразительность / мощность / сложность. Кроме того, членство каждого класса «красиво» демонстрируется некоторыми элементами (в отличие от проблемы высоты звезды, которая может быть проблематичной).$L$

Спасибо!

Вот список нескольких интересующих иерархий, некоторые из которых уже упоминались в других ответах.

1. Конкатенация иерархий

Язык $L$ является отмеченный продукт из $L_0, L_1, \ldots, L_n$ , если $L = L_0a_1L_1 \cdots a_nL_n$ для некоторых букв 1 , ... , п . Иерархии конкатенации определяются чередующимися логическими операциями и полиномиальными операциями (= объединение и помеченный продукт). Иерархия Штраубинга-Териена (отправная точка { ∅ , A ∗ } )$a_1, \ldots, a_n$$\{\emptyset, A^*\})\ $и иерархия глубины точек (начальная точка $\{\emptyset, \{1\}, A^+, A^*\})\ $ относится к этому типу, но вы можете выбрать другие начальные точки, в частности, групповые языки (языки, принятые автоматом перестановок).

2. Звездно-высотные иерархии

Общая схема состоит в подсчете минимального количества вложенных звездочек, необходимого для выражения языка, начинающегося с букв, но возможны несколько вариантов, в зависимости от того, какие основные операторы вы допускаете. Если вы разрешаете только объединение и произведение, вы определяете ограниченную высоту звезды, если вы разрешаете объединение, дополнение и произведение, вы определяете (обобщенную) высоту звезды, а если вы разрешаете объединение, пересечение и произведение, вы определяете промежуточную высоту звезды. , Существуют языки с ограниченным числом звездочек для каждого n, и он может эффективно вычислять высоту звезды данного обычного языка. Для высоты звезды звезда-высота 0 разрешима ( языки без звезды ), существуют языки высоты звезды $n$$n$$0$$1$, но язык звездной высоты не известен! На промежуточной высоте звезды неизвестен результат. Смотрите эту статью для обзора.$2$

3. Логические иерархии

Есть многие из них, но один из наиболее важных из них является так называемая иерархии. Формула называется Σ п -формула , если она эквивалентна формуле вида Q ( х 1 , . . . , Х к ) φ , где φ является квантификатором свободной и Q ( х 1 , . . . , Х k ) последовательность из $\Sigma_n$$\Sigma_n$$Q(x_1,...,x_k)\varphi$$\varphi$$Q(x_1,...,x_k)$$n$блоки кванторов таким образом, что первый блок содержит только кванторы существования (обратите внимание , что этот первый блок может быть пустым), второй блок универсальные кванторы и т.д. Аналогично, если формируется из п Чередуя блоки кванторов, начинающиеся с блока универсальных квантификаторов (который опять может быть пустым), мы говорим, что φ является Π n- формулой. Обозначим через Σ n (соответственно Π n ) класс языков, которые можно определить с помощью Σ n -формулы (соответственно a $Q(x_1,...,x_k)$$n$$\varphi$$\Pi_n$$\Sigma_n$$\Pi_n$$\Sigma_n$ формула) и B Σ n булево замыкание Σ n -языков. Пустьнаконец, Δ п = Σ п ∩ П п . Общая картина выглядит так. Нужно, конечно, указать подпись. Существует, как правило предикатадля каждой буквы (и через е средств есть буквав положении х в слове). Затем можно добавить двоичный символ$\Pi_n$$\mathcal{B}\Sigma_n$$\Sigma_n$$\Delta_n = \Sigma_n \cap \Pi_n$$\mathbf{a}$$\mathbf{a}x$$a$$x$$<$(соответствующая иерархия - иерархия Штраубинга-Териена), а также символ-преемник (соответствующая иерархия - иерархия глубины точек). Другие возможности включают в себя предиката, для подсчета по модулю N , и т.д. См снова эту бумагу для обзора.$Mod$$n$

4. Булевы иерархии

Общая закономерность (которая не характерна для обычных языков) обусловлена ​​Хаусдорфом. Пусть - класс языков, содержащий пустое множество и полный набор и замкнутый относительно конечного пересечения и конечного объединения. Пусть Д п ( Ь ) класс всех языков вида Х = Х 1 - Х 2 + ⋯ & plusmn ; Х п , где Х я ∈ L и X 1 ⊇ X 2 ⊇ X 3 ⊇ ⋯ ⊇ Х н . поскольку$\mathcal{L}$$\mathcal{D}_n(\mathcal{L})$

$$\begin{equation} X = X_1 - X_2 + \cdots \pm X_n \end{equation}$$ $X_i\in \mathcal{L}$$X_1 \supseteq X_2\supseteq X_3 \supseteq \cdots \supseteq X_n$, классы D п ( L ) определяют иерархию и их объединение логическое замыкание L . Опять же, возможны различные отправные точки.$\mathcal{D}_n(\mathcal{L}) \subseteq \mathcal{D}_{n+1}(\mathcal{L})$$\mathcal{D}_n(\mathcal{L})$$\mathcal{L}$

5. Групповая сложность

Результат Крона-Родса (1966) гласит, что каждый DFA может быть смоделирован каскадом автоматов сброса (также называемых триггером) и автоматами, полугруппы переходов которых являются конечными группами. Групповая сложность языка - это наименьшее количество групп, участвующих в такой декомпозиции минимального DFA языка. Языки сложности - это языки без звезд, и существуют языки любой сложности. Однако эффективная характеристика языков сложности 1 не известна.$0$$1$

6. Иерархии унаследованы от сложности схемы

Отправной точкой является хорошая статья которой, в частности, показано, что класс A C 0 ∩ R e g разрешим. Пусть A C C ( q ) = { L ⊆ { 0 , 1 } ∗ ∣ L ⩽ A C 0 M O D q } , где M O D q = { u ∈ { 0 , 1 $[1]$$AC^0 \cap Reg$$ACC(q) = \{ L \subseteq \{0,1\}^* \mid L \leqslant_{AC^0} MOD_q\}$ . Если q делит q ′ , то A C C ( q ) ⊆ A C C ( q ′ ) . Интересный вопрос состоит в том, чтобы узнать,разрешимали A C C ( q ) ∩ R e g для любого q .$MOD_q = \{u \in \{0,1\}^* \mid |u|_1 \equiv 0 \bmod q\}$$q$$q'$$ACC(q) \subseteq ACC(q')$$ACC(q) \cap Reg$$q$

Баррингтон, Дэвид А. Микс; Комптон, Кевин; Штраубинг, Говард; Териен, Денис. Обычные языки в N C 1 . J. Comput. System Sci. 44(1992)$[1]$$NC^1$

Расширяя комментарий: естественная иерархия - это та, которая вызвана количеством состояний DFA.

Мы можем определить $\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$

( , | Q | = n )$D = \{Q, \Sigma, \delta, q_0, F \}$$|Q| = n$

Ясно, что (просто используйте мертвые состояния)$\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$

Чтобы показать правильное включение мы можем просто выбрать язык: L n + 1 = { a i ∣ i ≥ n } ∈ L n + $\mathcal{L}_n \subsetneq \mathcal{L}_{n+1}$$L_{n+1} = \{ a^{i} \mid i \geq n \} \in \mathcal{L}_{n+1}$

Очень неформально: (минимальный) DFA, который распознает должен быть «цепочкой состояний» длиной n + 1 : q 0 → a q 1 → a . , , → a q n , F = { q n } и q n → a q n ( q n имеет самоконтроль). Так что n + 1 состояний достаточно, чтобы принять$\{ a^{i} \mid i \geq n \}$$n+1$$q_0 \to^a q_1 \to^a ... \to^a q_n$$F = \{q_n\}$$q_n \to^a q_n$$q_n$$n+1$ . Но каждый принимающий путь от q 0 до конечного состояния q f, который строго короче, чем n + 1, должен принимать некоторый a i с i < n, который не принадлежит L n + 1 , поэтому DFA с n или меньшим числом состояний не может принять L n + 1 .$L_{n+1}$$q_0$$q_f$$n+1$$a^{i}$$i < n$$L_{n+1}$$n$$L_{n+1}$

Недавно я наткнулся на эту статью, которая может привести другой соответствующий пример (см. Последнее предложение тезисов):

Гийом Бонфанте, Флориан Делуп: Род регулярных языков.

Из аннотации: в статье определен и изучен род конечных состояний детерминированных автоматов (ФСА) и регулярных языков. Действительно, FSA можно рассматривать как график, для которого возникает понятие рода. В то же время, FSA имеет семантику через свой базовый язык. Тогда естественно установить связь между языками и понятием рода. После того, как мы вводим и оправдываем понятие рода для регулярных языков, [...] мы строим регулярные языки произвольного большого рода: понятие рода определяет правильную иерархию регулярных языков.

Для обычных языков бесконечных слов существует несколько естественных иерархий, которые, например, передают понятие «сложность языка»:

• Количество рангов, необходимых в автомате детерминированной четности
• Вейджевая (или вагнеровская) иерархия: топологическая сложность, уровни .$\omega^\omega$

Эти иерархии могут быть обобщены для обычных языков бесконечных деревьев, для которых появляются новые иерархии, см., Например, этот ответ .