Revisi per 9 Februari 2021 23.32 sunting InternetArchiveBot (bicara \| kontrib) Bot 695.973 suntingan Add 1 book for Wikipedia:Pemastian (20210209)) #IABot (v2.0.8) (GreenC bot ← Revisi sebelumnya		Revisi terkini sejak 9 Mei 2021 15.56 sunting balikkan Rachmat04 (bicara \| kontrib) Birokrat, Pengurus antarmuka, Pengurus 66.241 suntingan k clean up, replaced: monoid sintaksis → monoid sintaktik using AWB
Baris 1: Dalam [[aljabar abstrak]], '''monoid bebas''' pada [[Himpunan (matematika) \| himpunan]] adalah [[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 λ, sebagai [[elemen identitas]]. Monoid bebas pada himpunan '' A '' biasanya dilambangkan ''A''<sup>&lowast;</sup>. '''Semigrup bebas''' di '' A '' adalah sub[[semigrup]] dari ''A''<sup>&lowast;</sup> mengandung semua elemen kecuali string kosong. Biasanya dilambangkan ''A''<sup>+</sup>.<ref name=Lot23>{{harvtxt\|Lothaire\|1997\|pp=2–3}}, [https://books.google.com/books?id=eATLTZzwW-sC&pg=PA2]</ref><ref name=PF2>{{harvtxt\|Pytheas Fogg\|2002\|p=2}}</ref> Secara lebih umum, sebuah monoid abstrak (atau setengah grup) '' S '' dideskripsikan sebagai '''bebas''' jika [[isomorfik]] ke monoid bebas (atau semigroup) pada beberapa set.<ref name=Lot5>{{harvtxt\|Lothaire\|1997\|p=5}}</ref> Sesuai dengan namanya, monoid dan semigroup bebas adalah objek yang memenuhi [[sifat universal]] yang biasa mendefinisikan [[objek bebas]], di masing-masing [[kategori (matematika) \| 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]]. Baris 15: <ref>Karena penambahan bilangan asli bersifat asosiatif, hasilnya tidak bergantung pada urutan evaluasi, sehingga memastikan pemetaan terdefinisi dengan baik.</ref> dan urutan kosong ke nol membentuk isomorfisme dari himpunan urutan tersebut ke '''N<sub>0</sub>'''. 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''<sup>&lowast;</sup> 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''<sup>&lowast;</sup> berisi semua rangkaian ''a'', ''b'', dan ''c'': Baris 26: Jika '' A '' ada yang disetel, fungsi '' panjang kata '' aktif ''A''<sup>&lowast;</sup> adalah [[homomorfisme monoid]] dari ''A''<sup>&lowast;</sup> ke ('''N<sub>0</sub>''',+) yang memetakan setiap elemen '' A '' ke 1. Monoid bebas dengan demikian adalah '''monoid bertingkat'''.<ref name=Sak382>Sakarovitch (2009) p.382</ref> (Sebuah monoid bertingkat <math> M </math> adalah sebuah monoid yang dapat ditulis sebagai <math>M=M_0\oplus M_1\oplus M_2 \cdots</math>. Setiap <math> M_n </math> adalah sebuah nilai; penilaian di sini hanyalah panjang string. Artinya, <math> M_n </math> berisi string dengan panjang tersebut <math>n.</math> The <math>\oplus</math> simbol di sini dapat diartikan "mengatur persatuan"; ini digunakan sebagai pengganti simbol <math>\cup</math> karena, secara umum, set union mungkin bukan monoid, dan simbol yang berbeda digunakan. Sesuai ketentuan, gradasi selalu ditulis dengan simbol <math>\oplus</math>.) Ada hubungan yang dalam antara teori [[semigrup]] dan [[teori automata \| automata]]. Misalnya, setiap bahasa formal memiliki [[monoid ~~sintaksis~~sintaktik]] 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.<ref> {{Cite book\|url=https://books.google.com/books?id=C5QbCAAAQBAJ\|title=Groups, Languages, Algorithms: AMS-ASL Joint Special Session on Interactions Between Logic, Group Theory, and Computer Science, January 16-19, 2003, Baltimore, Maryland\|last=Borovik\|first=Alexandre\|date=2005-01-01\|publisher=American Mathematical Soc.\|isbn=9780821836187\|language=en}} </ref> Untuk kasus [[komputasi serentak]], yaitu, sistem dengan [[kunci (ilmu komputer) \| 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 == [[Berkas:Example of strings equidivisibility.gif\|thumb\|Contoh untuk kasus pertama ekuidivisibilitas: m="UNCLE", n="ANLY", p="UN", q="CLEANLY", dan s="CLE"]] Kami mendefinisikan sepasang kata dalam ''A''<sup>&lowast;</sup> dari bentuk '' uv '' dan '' vu '' sebagai '' 'konjugasi' '': konjugasi sebuah kata adalah [[pergeseran melingkar]]-nya.<ref name=Sak27>Sakarovitch (2009) p.27</ref> Dua kata dikonjugasikan dalam pengertian ini jika mereka [[Konjugasi (teori grup) \| konjugasi dalam pengertian teori grup]] sebagai elemen dari [[grup bebas]] yang dihasilkan oleh ''A''.<ref name=PF297>{{harvtxt\|Pytheas Fogg\|2002\|p=297}}</ref> === Ekuidivisibilitas === Baris 58: == Proyeksi pita == Operasi dari [[Operasi pita#Proyeksi pita \| proyeksi pita]] adalah sebuah endomorfisme. Artinya, diberi rumus ''a'' ∈ Σ dan seutas pita ''s'' ∈ Σ<sup>&lowast;</sup>, proyeksi pita ''p''<sub>a</sub>(''s'') menghapus setiap kemunculan '' a '' dari '' s ''; itu secara formal didefinisikan oleh :<math>p_a(s) = \begin{cases} Baris 72: dimana <math>p_a\left(\Sigma^\right)</math> dipahami sebagai monoid bebas dari semua pita berhingga yang tidak mengandung huruf '' a ''. Proyeksi bolak-balik dengan pengoperasian rangkaian pita, sehingga <math>p_a(st)=p_a(s)p_a(t)</math> untuk semua string '' s '' dan '' t ''. Ada banyak pembalikan kanan untuk proyeksi string, dan karenanya ini adalah [[epimorfisme terpisah]]. Morfisme identitas adalah <math>p_\varepsilon,</math> didefinisikan sebagai <math>p_\varepsilon(s)=s</math> untuk pita 's', dan <math>p_\varepsilon(\varepsilon)=\varepsilon</math>. Proyeksi pita bersifat komutatif, dengan jelas Baris 84: :<math>p_a(p_a(s))=p_a(s)</math> untuk pita ''s''. Jadi, proyeksi adalah operasi idempoten, komutatif, dan karenanya membentuk [[semilatik]] berbatas atau komutatif [[band (aljabar) \| band]]. == Lihat pula == Baris 105: *{{Commons category-inline}} [[Kategori: Teori semigrup]] [[Kategori: Bahasa formal]] [[Kategori: Struktur aljabar gratis]] [[Kategori: Kombinatorik pada kata-kata]]

Monoid bebas: Perbedaan antara revisi