(N) DFA с таким же начальным / принимающим состоянием (ями)

Что известно о классе языков, распознаваемых конечными автоматами, имеющими одинаковое начальное и принимающее состояние? Это правильное подмножество обычных языков (поскольку каждый такой язык содержит пустую строку), но насколько он слаб? Есть ли простая алгебраическая характеристика?

То же самое для языков, распознаваемых недетерминированными автоматами с одинаковым набором начальных и принимающих состояний.

Этот вопрос решается для детерминированных автоматов и для однозначных автоматов в книге [1]

[1] Дж. Берстель, Д. Перрен, С, Рейтенауэр, Коды и автоматы, Vol. 129 из энциклопедии математики и ее приложений, издательство Кембриджского университета, 2009.

В случае детерминированных автоматов характеристика приведена в предложении 3.2.5. Напомним , что подмоноид из A * является право унитарным , если для всех U , v ∈ M , U , U v ∈ M означает , V ∈ M . $M$$A^*$$u, v \in M$$u, uv \in M$$v \in M$

Предложение . Пусть - правильное подмножество в A ∗ . Следующие условия эквивалентны:$L$$A^*$

1. - правый унитарный субмоноид,$L$
2. для некоторого префиксного кода P ,$L = P^*$$P$
3. Минимальный автомат имеет единственное конечное состояние, а именно начальное состояние.$L$
4. Существует детерминированный автомат, распознающий имеющее начальное состояние как уникальное конечное состояние.$L$

Для однозначных автоматов характеристика следует из теоремы 4.2.2 и может быть сформулирована следующим образом:

Предложение . Пусть - правильное подмножество в A ∗ . Следующие условия эквивалентны:$L$$A^*$

1. является свободным подмоноидом A ∗ ,$L$$A^*$
2. для некоторого кода C ,$L = C^*$$C$
3. Существует однозначный автомат, распознающий имеющее начальное состояние как уникальное конечное состояние.$L$

Наконец, для недетерминированных автоматов характеристика состоит в том, что является подмоноидом A ∗ .$L$$A^*$

$r^∗$$r$$r^*$

$q_0, \ldots, q_n$$q_0 = q_n$$n = 0$$q_0$

Важным подклассом этого семейства является подкласс 0-обратимых языков. Язык является 0-обратимым, если обращение минимального DFA для языка также является детерминированным. Операция реверса определяется как замена начальных и конечных состояний и инвертирование отношения краев DFA. Это означает, что 0-обратимый язык может иметь только одно принимающее состояние. Ваш вопрос добавляет еще одно ограничение, что это состояние должно быть начальным состоянием. Ваше ограничение не определяет 0-обратимые языки, потому что минимальный DFA для этих языков может иметь разные начальные и конечные состояния.

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

Вывод обратимых языков , Дана Англюин, Журнал ACM, 1982

Вы можете сослаться на полуцветковые автоматы, как говорится в их статье: «Полуэнергетический автомат (SFA) - это триммерный автомат с уникальным начальным состоянием, равным уникальному конечному состоянию, в котором все циклы должны пройти через начальное состояние ". См. «РАЗВИТИЕ ГОЛОНОМИИ КРУГЛЫХ ПОЛУЦВЕТОЧНЫХ АВТОМАТ» - Шубх Нараян Сингх, К.В. Кришна.