О реализации моноидов как синтаксических моноидов языков

Пусть - некоторый язык, тогда мы определим синтаксическую конгруэнцию как и фактор-моноид равен называется синтаксическим моноид из . $L \subseteq X^{\ast}$

u \sim v :\Leftrightarrow \forall x, y \in X^{*} : x u y \in L \leftrightarrow x v y \in L

$u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L$

X^{*} / \sim_{L}

$X^{\ast} / \sim_L$

L

$L$

Какие моноиды возникают как синтаксические моноиды языков? Я нашел языки для симметричных групп и для множества всех отображений на некотором конечном конечном множестве. Но как насчет других, существуют ли конечные моноиды, которые нельзя было бы записать как синтаксический моноид какого-либо языка?

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

Позвольте мне также отметить, что довольно просто реализовать любой конечный моноид как моноид преобразования некоторого автомата, просто взять элементы за состояния и рассмотреть каждый генератор как букву алфавита, и переходы даны при для некоторого состояния и буквы моноид преобразования изоморфен самому (это похоже на теорему Кэли о том, как группы встраиваются в симметрические группы). $M$ $M$ $M$ $qx$ $q$ $x$ $M$

fl.formal-languages automata-theory regular-language algebra monoid StefanH
источник

Что означает термин «язык» в этом контексте? Возможно, субмоноид? Редактировать. Ну, я думаю, что нет, так как это будет означать, что

всегда было отношением равенства. Возможно, они произвольные подмножества?

\sim

$\sim$

Гоблин

@goblin Язык - это просто произвольное подмножество

(т. е. множество конечных последовательностей или свободный моноид); они кодируют слова.

X^{*}

$X^{\ast}$

StefanH

Благодарю. Я начал догадываться так же. Есть ли связь между тем, что вы делаете здесь, и фактор-группой

где

G / N

$G/N$

нормальная подгруппа группы

? В любом случае, это выглядит очень круто.

N

$N$

G

$G$

Гоблин

@goblin Если вы ищете аналогию

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

X^{*}

$X^{\ast}$

\sim

$\sim$

G

$G$

N

$N$

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

L

$L$

StefanH

@goblin Может быть, еще одна аналогия, которая в некотором роде может быть знакома теоретику группы: учитывая язык

мы можем сформировать автомат (не обязательно конечный!) для принятия

(например, с правыми классами нерод). Теперь , если

обозначает состояния, то есть действие

, что дает отображение

. Теперь ядро этого действия как конгруэнтное отношение уточняет

тогда (но просто

L

$L$

L

$L$

Q

$Q$

Q \times X^{*} \to Q

$Q \times X^{\ast} \to Q$

X^{*} \to Q^{Q}

$X^{\ast} \to Q^Q$

\sim

$\sim$ сверху , как

q_{0} \cdot x u y = q_{0} \cdot x v y

$q_0\cdot xuy = q_0\cdot xvy$

u \sim v

$u\sim v$ может посылать их в разные конечные состояния, поэтому он может правильно уточнить

\sim

$\sim$

StefanH

Ответы:

Кажется, есть статья, отвечающая на этот точный вопрос, и даже в более общем случае регулярных языков, но я не могу найти версию открытого доступа. Если кто-то найдет ссылку без платного доступа, это было бы здорово. Я запросил полный текст на ResearchGate. $\omega$

Название : Какие конечные моноиды являются синтаксическими моноидами рациональных омега-языков .

Авторы : Фан Чунг Хай, Игорь Литовский, До Лонг Ван

Аннотация : Введено понятие ω-жестких множеств для конечного моноида. Мы доказываем, что конечный моноид M является синтаксическим моноидом Арнольда некоторого рационального ω-языка (для краткости ω-синтаксический) тогда и только тогда, когда существует ω-жесткое множество для M. Это свойство показано разрешимым для конечных моноидов. , Установлена связь между семейством ω-синтаксических моноидов и семейством ∗ -синтаксических моноидов (т. Е. Синтаксических моноидов рациональных языков конечных слов).

Кроме того, на странице Википедии о синтаксических моноидах говорится:

Каждый конечный моноид гомоморфен синтаксическому моноиду некоторого нетривиального языка [1], но не каждый конечный моноид изоморфен синтаксическому моноиду. [2]
Каждая конечная группа изоморфна синтаксическому моноиду некоторого нетривиального языка. [1]

[1] Макнотон, Роберт; Паперт, Сеймур (1971). Безконтактные автоматы. Исследовательская монография 65. С приложением Уильяма Хеннемана. MIT Press. п. 48. ISBN 0-262-13076-9. Zbl 0232,94024.

[2] Лоусон (2004) с.233

Денис
источник

Что значит «гомоморфный»? То есть, в каком направлении идет гомоморфизм, и нужно ли быть сюръективным?

Эмиль Йержабек 3

Это означает, что любой конечный моноид является субмоноидом синтаксического моноида. Это подтверждается в kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf

Денис

Просто примечание: публикации RIMS о заседаниях групп автоматов обычно не рецензируются. Так что будьте осторожны с содержанием, если вы не можете проверить их самостоятельно.

Питер Лейпольд

Более элементарно, чем ответ Дениса, следующее извлечено из «Теорий вычислимости» Пиппенгера, стр.87, и требует немедленной проверки.

$M$ $Y \subseteq M$ $\equiv_Y$ $M$ $x \equiv_Y y$ $\big[\forall w, z \in M$ $wxz \in Y \Leftrightarrow wyz \in Y\big]$

$M$ $Y \subseteq M$ $x \equiv_Y y \Rightarrow x = y$ $x, y \in M$ $M \approx M/\equiv_Y$

$M$

Михаэль Кадилхак
источник

$P$ $M$ $P$ $M$ является отношение равенства. Таким образом, моноид является синтаксическим моноидом языка тогда и только тогда, когда он содержит дизъюнктивное подмножество.

$\{1, a, b, c\}$ $1$ $xy = y$ $x, y \in \{a,b,c\}$

J.-E. Штырь
источник