Pada realisasi monoids sebagai monoids sintaksis bahasa

Biarkan $L \subseteq X^{\ast}$ menjadi bahasa tertentu, maka kita mendefinisikan kongruensi sintaksis sebagai dan hasil bagi monoid disebut monoid sintaksis dari .

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$

Sekarang monoids apa yang muncul sebagai monoids sintaksis bahasa? Saya menemukan bahasa untuk grup simetris dan untuk set semua pemetaan pada beberapa set hingga yang mendasarinya. Tetapi bagaimana dengan yang lain, adakah monoida terbatas yang tidak dapat ditulis sebagai mono sintaksis dari suatu bahasa?

Untuk otomat tertentu, dengan mempertimbangkan monoid yang dihasilkan oleh pemetaan yang diinduksi oleh huruf-huruf di negara-negara (yang disebut transformasi monoid) ketika komposisi fungsi dibaca dari kiri ke kanan, ia berpendapat bahwa mono transformasi dari otomat minimal adalah tepat. mono sintaksis. Pengamatan ini membantu saya dalam membangun contoh-contoh yang disebutkan di atas.

Biar saya juga tidak cukup sederhana untuk mewujudkan setiap monoid terbatas sebagai monoid transformasi dari beberapa robot, cukup ambil elemen-elemen sebagai status, dan anggap setiap generator sebagai huruf alfabet dan transisi diberikan oleh untuk beberapa keadaan dan huruf , maka transformasi monoid adalah isomorfik untuk itu sendiri (ini mirip dengan teorema Cayley tentang bagaimana kelompok menanamkan ke dalam kelompok simetris). $M$ $M$ $M$ $qx$ $q$ $x$ $M$

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

Apa arti istilah "bahasa" dalam konteks ini? Submonoid, mungkin? Edit. Yah, saya kira bukan itu, karena ini berarti bahwa

selalu merupakan hubungan persamaan Mungkin mereka himpunan bagian yang sewenang-wenang?

\sim

$\sim$

goblin

@ goblin Bahasa hanyalah beberapa subset sewenang-wenang dari

(yaitu serangkaian sekuens terbatas, atau monoid bebas); mereka menyandikan kata-kata.

X^{*}

$X^{\ast}$

StefanH

Terima kasih. Aku mulai menduga. Apakah ada hubungan antara apa yang Anda lakukan di sini dan grup hasil bagi

mana

adalah subkelompok normal dari grup

? Either way, ini sepertinya sangat keren.

G / N

$G/N$

N

$N$

G

$G$

goblin

@ goblin Jika Anda mencari analogi

dan

dengan

dan

, maka saya tidak melihat hubungan langsung apa pun kecuali abstrak yang membentuk struktur faktor (dan karenanya mendorong morfisme kanonik); tetapi ada cara-cara lain bahwa kelompok dapat memasukkan gambar di sini, misalnya monoid sintaksis dapat berupa grup, atau

juga dapat menjadi grup (yang digeneralisasikan ke gagasan kelompok otomatis, saya kira, tetapi saya bukan ahli di sini). Saya sarankan Anda membuka posting baru jika Anda tertarik bagaimana grup dapat memasuki panggung di sini!

X^{*}

$X^{\ast}$

\sim

$\sim$

G

$G$

N

$N$

L

$L$

StefanH

@ goblin Mungkin analogi lain yang dalam beberapa hal mungkin akrab dengan ahli teori grup: Diberi bahasa

kita dapat membentuk automaton (tidak perlu terbatas!) untuk menerima

(misalnya dengan kelas kanan nerode). Sekarang jika

menunjukkan negara-negara, maka kita memiliki tindakan

, yang memberikan pemetaan

. Sekarang inti dari aksi ini sebagai relasi kongruensi memurnikan

dari atas sebagai

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$ kemudian (tetapi hanya

dapat mengirim mereka ke keadaan akhir yang berbeda, maka itu dapat dengan baik memperbaiki

u \sim v

$u\sim v$

\sim

$\sim$

StefanH

Jawaban:

Tampaknya ada sebuah makalah menjawab pertanyaan ini dengan tepat, dan bahkan dalam kasus yang lebih umum dari bahasa -regular, tapi saya tidak dapat menemukan versi open-akses. Jika seseorang menemukan tautan tanpa paywall, itu akan bagus. Saya meminta teks lengkap tentang ResearchGate. $\omega$

Judul : Monoids Hingga yang merupakan Monoids Sintaksis dari omega-Bahasa Rasional .

Penulis : Phan Trung Huy, Igor Litovsky, Do Long Van

Abstrak : Gagasan set ω-kaku untuk monoid terbatas diperkenalkan. Kami membuktikan bahwa monoid terbatas M adalah monoid sintaksis Arnold dari beberapa bahasa ω rasional (ω-sintaksis singkatnya) jika dan hanya jika ada set ω-kaku untuk M. Properti ini terbukti dapat diperintah untuk monoida terbatas . Hubungan antara keluarga monoids sintaksis and dan keluarga monoids sintaksis (yaitu monoid sintaksis bahasa rasional dari kata-kata terbatas) terjalin.

Selain itu, halaman wikipedia pada status mono sintaksis:

Setiap monoid terbatas adalah homomorfik dengan monoid sintaksis dari beberapa bahasa non-sepele, [1] tetapi tidak setiap monoid terbatas adalah isomorfik untuk monoid sintaksis. [2]
Setiap kelompok hingga isomorfik dengan monoid sintaksis dari beberapa bahasa non-sepele. [1]

[1] McNaughton, Robert; Papert, Seymour (1971). Automata bebas-counter. Research Monograph 65. Dengan lampiran oleh William Henneman. MIT Press. hal. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004) hal.233

Denis
sumber

Apa artinya "homomorfik"? Yaitu, ke arah mana homomorfisme berjalan, dan apakah itu harus bersifat surjektif?

Emil Jeřábek mendukung Monica

Ini berarti bahwa setiap monoid terbatas adalah submonoid dari monoid sintaksis. Ini dikonfirmasi dalam kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf

Denis

Hanya sebuah catatan: publikasi RIMS dari rapat grup automata biasanya tidak disorot. Jadi berhati-hatilah dalam hal konten, jika Anda tidak dapat memverifikasi sendiri.

Peter Leupold

Dalam cara yang lebih mendasar daripada jawaban Denis, berikut ini diambil dari "Theory of Computability" Pippenger, hal.87, dan segera diperiksa.

Definisi: Misalkan menjadi monoid, dan . Tentukan hubungan kongruensi lebih dari dengan iff , . $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]$

Definisi: Biarkan menjadi monoid. Sebuah subset adalah kaku jika untuk semua . (Setara, ) $M$ $Y \subseteq M$ $x \equiv_Y y \Rightarrow x = y$ $x, y \in M$ $M \approx M/\equiv_Y$

Teorema: monoid terbatas adalah monoid sintaksis dari beberapa bahasa reguler jika memiliki subset yang kaku. $M$

Tentu saja, makhluk yang terbatas, properti ini decidable. $M$

Michaël Cadilhac
sumber

Terminologi yang kaku tampaknya relatif baru dibandingkan dengan istilah disjungtif yang digunakan pada akhir 70-an (dan mungkin sebelumnya, saya tidak memeriksa referensi sebelumnya). Sebuah subset dari monoid adalah disjungtif jika dan hanya jika kesesuaian sintaksis dari di adalah hubungan kesetaraan. Dengan demikian monoid adalah monoid sintaksis dari suatu bahasa jika dan hanya jika mengandung subset disjungtif. $P$ $M$ $P$ $M$

Dengan karakterisasi ini, mudah untuk menemukan monoida terbatas yang bukan mono sintaksis dari bahasa apa pun: ambil monoid di mana adalah identitas dan sisa penggandaan didefinisikan oleh untuk semua . Hasil ini adalah cerita rakyat (<1980). $\{1, a, b, c\}$ $1$ $xy = y$ $x, y \in \{a,b,c\}$

J.-E. Pin
sumber