Monoid bebas

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 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*&lowast;. **Semigrup bebas** di * A * adalah subsemigrup dari *A*&lowast; mengandung semua elemen kecuali string kosong. Biasanya dilambangkan *A*+.

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

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 (**N<sub>0</sub>**,+) 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

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*&lowast; 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*&lowast; berisi semua rangkaian *a*, *b*, dan *c*:
:{ε, *a*, *ab*, *ba*, *caa*, **', ...}.

Jika '' A '' ada yang disetel, fungsi '' panjang kata '' aktif ''A''<sup>&lowast;</sup> adalah [[homomorfisme monoid]] dari ''A''<sup>&lowast;</sup> ke (**N0**,+) yang memetakan setiap elemen '' A '' ke 1. Monoid bebas dengan demikian adalah **monoid bertingkat**. (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 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.

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

Kami mendefinisikan sepasang kata dalam ''A''<sup>&lowast;</sup> dari bentuk '' uv '' dan '' vu '' sebagai '' 'konjugasi' '': konjugasi sebuah kata adalah [[pergeseran melingkar]]-nya.  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''.

=== 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''. Hasil ini juga dikenal sebagai [[lemma Levi]].

Sebuah monoid bebas jika dan hanya jika bertingkat dan equidivisible.

== 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''<sup>&lowast;</sup> is again free.  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** 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''<sup>&lowast;</sup> adalah morfisme dari ''A''<sup>&lowast;</sup> to itself.  [[Peta identitas]] '' I '' adalah endomorfisme dari ''A''<sup>&lowast;</sup>, 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 *.

== Proyeksi pita ==
Operasi dari [[Operasi pita#Proyeksi pita|proyeksi pita]] adalah sebuah endomorfisme. Artinya, diberi rumus *a* &isin; &Sigma; dan seutas pita *s* &isin; &Sigma;<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} 
\varepsilon & \text{jika } s=\varepsilon, \text{ pita kosong} \\
p_a(t) & \text{jika } s=ta  \\ 
p_a(t)b & \text{jika } s=tb \text{ dan } b\ne a.   
\end{cases}</math>

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

:<math>p_a\left(\Sigma^*\right)= \left(\Sigma-a\right)^*</math>

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

:<math>p_a(p_b(s))=p_b(p_a(s)).</math>

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

:<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.

## Lihat pula
* Operasi pita

## Catatan

## Referensi
* 
* 
*
* 
*
* 
* 
* 

## Pranala luar
*