Monoid bebas

monoid yang semua elemennya adalah urutan hingga (atau string) dari nol atau lebih elemen dari himpunan, dengan penggabungan pita sebagai operasi monoid dan dengan urutan unik elemen nol, sering disebut pita kosong dan dilambangkan dengan ε atau λ
Revisi sejak 25 November 2020 04.11 oleh 123569yuuift (bicara | kontrib) (Membuat halaman baru)
(beda) ← Revisi sebelumnya | Revisi terkini (beda) | Revisi selanjutnya → (beda)

Dalam aljabar abstrak, monoid bebas pada himpunan adalah monoid yang semua elemennya adalah urutan hingga (atau string) dari nol atau lebih elemen dari himpunan, dengan string concatenation sebagai operasi monoid dan dengan urutan unik elemen nol, sering disebut pita kosong dan dilambangkan dengan ε atau λ, sebagai elemen identitas. Monoid bebas pada himpunan A biasanya dilambangkan A. Semigrup bebas di A adalah subsemigrup dari A mengandung semua elemen kecuali string kosong. Biasanya dilambangkan A+.[1][2]

Secara lebih umum, sebuah monoid abstrak (atau setengah grup) S dideskripsikan sebagai bebas jika isomorfik ke monoid bebas (atau semigroup) pada beberapa set.[3]

Sesuai dengan namanya, monoid dan semigroup bebas adalah objek yang memenuhi sifat universal yang biasa mendefinisikan objek bebas, di masing-masing kategori dari monoid dan semigroup. Oleh karena itu, setiap monoid (atau semigrup) muncul sebagai citra homomorfik dari monoid bebas (atau semigrup). Studi tentang semigroup sebagai gambar dari semigrup bebas disebut teori semigroup kombinatorial.

Monoid bebas (dan monoid pada umumnya) adalah asosiatif, menurut definisi; artinya, mereka ditulis tanpa tanda kurung untuk menunjukkan pengelompokan atau urutan operasi. Padanan non-asosiatifnya adalah magma bebas.

Contoh

Bilangan asli

Monoid (N0,+) dari bilangan asli (termasuk nol) yang ditambahkan adalah monoid bebas pada generator bebas tunggal, dalam hal ini bilangan asli 1. Menurut definisi formalnya, monoid ini terdiri dari semua urutan seperti "1", "1 + 1", "1 + 1 + 1", "1 + 1 + 1 + 1", dan seterusnya, termasuk barisan kosong. Memetakan setiap urutan tersebut ke hasil evaluasinya [4] dan urutan kosong ke nol membentuk isomorfisme dari himpunan urutan tersebut ke N0. Isomorfisma ini kompatibel dengan "+", yaitu, untuk dua urutan s dan t , jika s dipetakan (yaitu dievaluasi) ke nomor m dan t ke n, untuk rangkaian s+t

Bintang Kleene

Dalam teori bahasa formal, biasanya serangkaian "simbol" A (kadang-kadang disebut alfabet) dianggap terbatas. Urutan simbol yang terbatas disebut "kata di atas A ", dan monoid bebas A disebut "Bintang Kleene dari A ". Dengan demikian, studi abstrak bahasa formal dapat dianggap sebagai studi subset dari monoid bebas yang dihasilkan tanpa batas.

Misalnya, dengan asumsi alfabet A = {a, b, c}, bintang Kleene-nya A berisi semua rangkaian a, b, dan c:

{ε, a, ab, ba, caa, cccbabbc, ...}.

Jika A ada yang disetel, fungsi panjang kata aktif A adalah homomorfisme monoid dari A ke (N0,+) yang memetakan setiap elemen A ke 1. Monoid bebas dengan demikian adalah monoid bertingkat.[5] (Sebuah monoid bertingkat   adalah sebuah monoid yang dapat ditulis sebagai  . Setiap   adalah sebuah nilai; penilaian di sini hanyalah panjang string. Artinya,   berisi string dengan panjang tersebut   The   simbol di sini dapat diartikan "mengatur persatuan"; ini digunakan sebagai pengganti simbol   karena, secara umum, set union mungkin bukan monoid, dan simbol yang berbeda digunakan. Sesuai ketentuan, gradasi selalu ditulis dengan simbol  .)

Ada hubungan yang dalam antara teori semigrup dan automata. Misalnya, setiap bahasa formal memiliki monoid sintaksis yang mengenali bahasa tersebut. Untuk kasus bahasa reguler, monoid itu isomorfik ke transisi monoid yang terkait dengan semiautomaton dari beberapa automaton terbatas deterministik yang mengenali bahasa. Bahasa reguler di atas alfabet A adalah penutupan dari himpunan bagian hingga A*, monoid bebas di atas A, di bawah penyatuan, produk, dan pembuatan submonoid.[6]

Untuk kasus komputasi serentak, yaitu, sistem dengan kunci, mutex atau benang gabungan, komputasi dapat dijelaskan dengan sejarah monoid dan jejak monoid. Secara kasar, elemen monoid dapat melakukan perjalanan, (mis, utas yang berbeda dapat dijalankan dalam urutan apa pun), tetapi hanya hingga kunci atau mutex, yang mencegah pergantian lebih lanjut (mis, membuat serial akses utas ke beberapa objek).

Kata konjugasi

 
Contoh untuk kasus pertama ekuidivisibilitas: m="UNCLE", n="ANLY", p="UN", q="CLEANLY", dan s="CLE"

Kami mendefinisikan sepasang kata dalam A dari bentuk uv dan vu sebagai 'konjugasi' : konjugasi sebuah kata adalah pergeseran melingkar-nya.[7] Dua kata dikonjugasikan dalam pengertian ini jika mereka konjugasi dalam pengertian teori grup sebagai elemen dari grup bebas yang dihasilkan oleh A.[8]

Ekuidivisibilitas

Monoid bebas adalah equidivisible: jika persamaan mn = pq berlaku, maka terdapat s sehingga m = ps, sn = q (contoh lihat gambar) atau ms = p, n = sq.[9] Hasil ini juga dikenal sebagai lemma Levi.[10]

Sebuah monoid bebas jika dan hanya jika bertingkat dan equidivisible.[9]

Faktorisasi

Faktorisasi dari monoid bebas adalah urutan himpunan bagian kata dengan sifat bahwa setiap kata dalam monoid bebas dapat dituliskan sebagai rangkaian elemen yang diambil dari himpunan bagian tersebut. Teorema Chen–Fox–Lyndon menyatakan bahwa Kata Lyndon memberikan faktorisasi. Secara lebih umum, Kata Hall memberikan faktorisasi; kata-kata Lyndon adalah kasus khusus dari kata-kata Hall.

Lambung bebas

Perpotongan submonoids bebas dari monoid bebas A is again free.[11][12] Jika S adalah himpunan bagian dari monoid bebas A * maka perpotongan semua submonoid bebas dari A * yang mengandung S terdefinisi dengan baik, karena A * sendiri bebas, dan mengandung S ; itu adalah monoid bebas dan disebut lambung bebas dari S. Basis dari persimpangan ini adalah sebuah kode.

Teorema cacat[11][12][13] menyatakan bahwa jika X terbatas dan C adalah dasar dari lambung bebas X , maka salah satu X adalah kode dan C = X , atau

|C| ≤ |X| − 1 .

Endomorfisme

Endomorfisme pada A adalah morfisme dari A to itself.[14] Peta identitas I adalah endomorfisme dari A, dan endomorfisme membentuk monoid di bawah komposisi fungsi.

Endomorfisme f adalah perpanjangan jika ada huruf a sedemikian rupa sehingga f(a) = as untuk pita yang tidak kosong s .[15]

Proyeksi pita

Operasi dari proyeksi pita adalah sebuah endomorfisme. Artinya, diberi rumus a ∈ Σ dan seutas pita s ∈ Σ, proyeksi pita pa(s) menghapus setiap kemunculan a dari s ; itu secara formal didefinisikan oleh

 

Perhatikan bahwa proyeksi pita terdefinisi dengan baik bahkan jika peringkat monoid tidak terbatas, karena definisi rekursif di atas berfungsi untuk semua string dengan panjang terbatas. Proyeksi pita adalah morfisme dalam kategori monoid bebas, sehingga

 

dimana   dipahami sebagai monoid bebas dari semua pita berhingga yang tidak mengandung huruf a . Proyeksi bolak-balik dengan pengoperasian rangkaian pita, sehingga   untuk semua string s dan t . Ada banyak pembalikan kanan untuk proyeksi string, dan karenanya ini adalah epimorfisme terpisah.

Morfisme identitas adalah   didefinisikan sebagai   untuk pita 's', dan  .

Proyeksi pita bersifat komutatif, dengan jelas

 

Untuk monoid bebas dengan pangkat terbatas, ini mengikuti dari fakta bahwa monoid bebas dengan pangkat yang sama bersifat isomorfik, karena proyeksi mengurangi pangkat monoid satu per satu.

Proyeksi pita adalah idempoten, sebagai

 

untuk pita s. Jadi, proyeksi adalah operasi idempoten, komutatif, dan karenanya membentuk semilatik berbatas atau komutatif band.

Lihat pula

Catatan

  1. ^ (Lothaire 1997, hlm. 2–3), [1]
  2. ^ (Pytheas Fogg 2002, hlm. 2)
  3. ^ (Lothaire 1997, hlm. 5)
  4. ^ Karena penambahan bilangan asli bersifat asosiatif, hasilnya tidak bergantung pada urutan evaluasi, sehingga memastikan pemetaan terdefinisi dengan baik.
  5. ^ Sakarovitch (2009) p.382
  6. ^ Borovik, Alexandre (2005-01-01). Groups, Languages, Algorithms: AMS-ASL Joint Special Session on Interactions Between Logic, Group Theory, and Computer Science, January 16-19, 2003, Baltimore, Maryland (dalam bahasa Inggris). American Mathematical Soc. ISBN 9780821836187. 
  7. ^ Sakarovitch (2009) p.27
  8. ^ (Pytheas Fogg 2002, hlm. 297)
  9. ^ a b Sakarovitch (2009) p.26
  10. ^ Aldo de Luca; Stefano Varricchio (1999). Finiteness and Regularity in Semigroups and Formal Languages. Springer Berlin Heidelberg. hlm. 2. ISBN 978-3-642-64150-3. 
  11. ^ a b (Lothaire 1997, hlm. 6)
  12. ^ a b (Lothaire 2011, hlm. 204)
  13. ^ (Berstel, Perrin & Reutenauer 2010, hlm. 66)
  14. ^ (Lothaire 2011, hlm. 450)
  15. ^ Allouche & Shallit (2003) p.10

Referensi

Pranala luar