Zur Realisierung von Monoiden als syntaktische Sprachmonoide

Let einige Sprache sein, dann definieren wir die syntaktische Kongruenz als und der Quotient monoid ist die angerufene syntaktische Monoid von . $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$

Welche Monoide entstehen nun als syntaktische Monoide von Sprachen? Ich fand Sprachen für symmetrische Gruppen und für die Menge aller Zuordnungen auf einer zugrunde liegenden endlichen Menge. Aber was ist mit anderen, gibt es endliche Monoide, die nicht als syntaktisches Monoid einer Sprache geschrieben werden könnten?

Betrachtet man für einen gegebenen Automaten das Monoid, das durch die durch die Buchstaben auf den Zuständen induzierten Abbildungen erzeugt wird (das sogenannte Transformationsmonoid), wenn die Funktionszusammensetzung von links nach rechts gelesen wird, so ist das Transformationsmonoid des Minimalautomaten genau das syntaktisches Monoid. Diese Beobachtung half mir bei der Konstruktion der oben genannten Beispiele.

Lassen Sie mich auch nicht sagen, dass es ganz einfach ist, ein endliches Monoid als Transformationsmonoid eines Automaten zu realisieren. Nehmen Sie einfach die Elemente von als Zustände und betrachten Sie jeden Generator von als Buchstaben des Alphabets, und die Übergänge sind gegeben durch für einen Zustand und einen Buchstaben ist das Transformationsmonoid zu selbst isomorph (dies ist ähnlich dem Cayley-Theorem darüber, wie Gruppen in symmetrische Gruppen eingebettet werden). $M$ $M$ $M$ $qx$ $q$ $x$ $M$

fl.formal-languages automata-theory regular-language algebra monoid StefanH
quelle

Was bedeutet der Begriff "Sprache" in diesem Zusammenhang? Vielleicht ein Submonoid? Bearbeiten. Nun, ich denke nicht, da dies bedeuten würde, dass

immer die Gleichheitsrelation war. Vielleicht sind sie willkürliche Teilmengen?

\sim

$\sim$

Kobold

@goblin Eine Sprache ist nur eine beliebige Teilmenge von

(dh eine Menge endlicher Sequenzen oder das freie Monoid); sie kodieren Wörter.

X^{*}

$X^{\ast}$

StefanH

Vielen Dank. Ich fing an, das zu vermuten. Gibt es einen Zusammenhang zwischen dem, was Sie hier tun, und der Quotientengruppe

wobei

eine normale Untergruppe einer Gruppe

? In jedem Fall scheint das sehr cool zu sein.

G / N

$G/N$

N

$N$

G

$G$

Kobold

@goblin Wenn Sie nach einer Analogie

und

suchen , dann sehe ich keine direkte Beziehung, nur dann, wenn es um die abstrakte Formung von Faktorstrukturen (und damit um die Induzierung kanonischer Morphismen) geht. Es gibt aber auch andere Möglichkeiten, wie Gruppen in dieses Bild eintreten können, beispielsweise könnte das syntaktische Monoid eine Gruppe sein, oder

könnte auch eine Gruppe sein (was den Begriff der automatischen Gruppen verallgemeinert, aber ich bin hier kein Experte). Ich würde vorschlagen, dass Sie einen neuen Beitrag eröffnen, wenn Sie daran interessiert sind, wie Gruppen hier die Bühne betreten können!

X^{*}

$X^{\ast}$

\sim

$\sim$

G

$G$

N

$N$

L

$L$

StefanH

@goblin Vielleicht eine andere Analogie, die dem Gruppentheoretiker vielleicht bekannt ist: Wenn eine Sprache

, können wir einen Automaten bilden (nicht unbedingt endlich!), um

zu akzeptieren (zum Beispiel mit den richtigen Klassen). Nun , wenn

die Zustände bezeichnet, dann haben wir eine Aktion

, die eine Zuordnung gibt

. Nun verfeinert der Kern dieser Aktion als Kongruenzrelation

von oben als

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$ dann (aber nur

kann sie in verschiedene Endzustände schicken, daher kann es richtig verfeinern

u \sim v

$u\sim v$

\sim

$\sim$

StefanH

Antworten:

Offenbar gibt es ein Papier, das genau diese Frage beantwortet, und das gilt auch für den allgemeineren Fall von regulären Sprachen, aber ich finde keine Open-Access-Version. Wenn jemand einen Link ohne Paywall findet, wäre das großartig. Ich habe den Volltext zu ResearchGate angefordert. $\omega$

Titel : Welche Finite Monoide sind syntaktische Monoide von Rational Omega-Sprachen .

Autoren : Phan Trung Huy, Igor Litovsky und Do Long Van

Abstract : Es wird ein Begriff von ω-starren Mengen für ein endliches Monoid eingeführt. Wir beweisen, dass ein endliches Monoid M das syntaktische Monoid nach Arnold einer rationalen ω-Sprache (kurz ω-syntaktisch) ist, wenn und nur dann eine ω-starre Menge für M existiert. Diese Eigenschaft ist für die endlichen Monoide entscheidbar . Die Beziehung zwischen der Familie der ω-syntaktischen Monoide und der der ∗-syntaktischen Monoide (dh der syntaktischen Monoide rationaler Sprachen endlicher Wörter) wird hergestellt.

Darüber hinaus heißt es auf der Wikipedia-Seite zu syntaktischen Monoiden:

Jedes endliche Monoid ist homomorph zu dem syntaktischen Monoid einer nicht-trivialen Sprache, [1] aber nicht jedes endliche Monoid ist isomorph zu einem syntaktischen Monoid. [2]
Jede endliche Gruppe ist isomorph zum syntaktischen Monoid einer nicht-trivialen Sprache. [1]

[1] McNaughton, Robert; Papert, Seymour (1971). Zählerfreie Automaten. Forschungsmonographie 65. Mit einem Anhang von William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004), S. 233

Denis
quelle

Was bedeutet "homomorph zu"? Das heißt, in welche Richtung geht der Homomorphismus und muss er surjektiv sein?

Emil Jeřábek unterstützt Monica am

Es bedeutet, dass jedes endliche Monoid ein Submonoid eines syntaktischen Monoids ist. Dies wird in kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf

Denis

Nur ein Hinweis: Die RIMS-Veröffentlichungen der Automatengruppensitzungen werden in der Regel nicht referiert. Gehen Sie also vorsichtig mit dem Inhalt um, wenn Sie ihn nicht selbst überprüfen können.

Peter Leupold

In einer elementareren Weise als Denis 'Antwort wird das Folgende aus Pippengers "Theories of Computability", S. 87, extrahiert und sofort überprüft.

$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$

Michaël Cadilhac
quelle

$P$ $M$ $P$ $M$

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

J.-E. Stift
quelle