Jelaskan Bintang Kleene dari Monoid bebas

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, , ...}.

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. (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 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, 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).