Rasyonel küme - Rational set

Gelen bilgisayar bilimleri , daha doğrusu içinde otomata teorisi , bir rasyonel seti a Monoid tüm sonlu alt kümelerini içerir ve altında kapalı olan bu Monoid alt kümelerine minimal sınıfının bir öğesidir birlik , ürün ve Kleene yıldızı . Rasyonel kümeler, otomata teorisinde , biçimsel dillerde ve cebirde faydalıdır .

Rasyonel bir küme, rasyonel (düzenli) dil kavramını ( düzenli ifadelerle tanımlandığı gibi anlaşılır ) zorunlu olarak özgür olmayan monoidlere genelleştirir .

Tanım

kimlik öğesi olan bir monoid olsun . Seti rasyonel alt kümelerinin her sonlu kümesi içerir ve altında kapalı olan en küçük kümesidir ${\görüntüleme stili (N,\cdot )}$${\görüntüleme stili e}$${\displaystyle \mathrm {RAT} (N)}$${\görüntüleme stili N}$

• birlik : eğer öyleyse${\displaystyle A,B\in \mathrm {RAT} (N)}$${\displaystyle A\cup B\in \mathrm {RAT} (N)}$
• ürün: eğer öyleyse${\displaystyle A,B\in \mathrm {RAT} (N)}$${\displaystyle A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)}$
• Kleene yıldızı : eğer o zaman nerede kimlik unsuru içeren tekil ve nerede .${\displaystyle A\in \mathrm {RAT} (N)}$${\displaystyle A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)}$${\ Displaystyle A^{0}=\{e\}}$${\displaystyle A^{n+1}=A^{n}\cdot A}$

Bu, herhangi bir rasyonel alt kümesinin, sonlu sayıda sonlu alt kümeleri alarak ve birleşim, çarpım ve Kleene yıldız işlemlerini sonlu sayıda uygulayarak elde edilebileceği anlamına gelir . ${\görüntüleme stili N}$${\görüntüleme stili N}$

Genel olarak bir monoidin rasyonel bir altkümesi bir altmonoid değildir.

Misal

Izin bir olmak alfabe , set kelimelerin üzerinde bir monoid olduğunu. rasyonel alt kümesi tam olarak düzenli dillerdir . Gerçekten de, düzenli diller sonlu bir düzenli ifade ile tanımlanabilir . ${\görüntüleme stili A}$${\görüntüleme stili A^{*}}$${\görüntüleme stili A}$${\görüntüleme stili A^{*}}$

Rasyonel alt kümeleri , nihai olarak tamsayıların periyodik kümeleridir. Daha genel olarak rasyonel alt kümeleri olan semilinear setleri . ${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} ^{k}}$

Özellikleri

McKnight'ın teoremi , eğer sonlu olarak üretilirse, o zaman tanınabilir alt kümesinin rasyonel kümeler olduğunu belirtir. Bu genel olarak doğru değildir, çünkü bütün her zaman tanınabilirdir, ancak sonsuz olarak üretiliyorsa rasyonel değildir . ${\görüntüleme stili N}$${\görüntüleme stili N}$${\görüntüleme stili N}$

Rasyonel kümeler morfizm altında kapalıdır: verilen ve iki monoid ve eğer öyleyse bir morfizm . ${\görüntüleme stili N}$${\görüntüleme stili M}$${\displaystyle \phi :N\sağ ok M}$${\displaystyle S\in \mathrm {RAT} (N)}$${\displaystyle \phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {RAT} (M)}$

${\displaystyle \mathrm {RAT} (N)}$aşağıdaki örnekte gösterildiği gibi tamamlayıcı altında kapalı değildir . Let , kümeler ve rasyoneldir, ancak ikinci elemana izdüşümü rasyonel olmadığı için değildir. ${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}}$${\displaystyle R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\ \mathbb {N} \}} içinde$${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(a^{n},b^{m}c^{n})\mid n,m\ \mathbb {N} \}} içinde$${\displaystyle R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}}$${\displaystyle \{b^{n}c^{n}\mid n\in \mathbb {N} \}}$

Rasyonel bir altkümenin ve tanınabilir bir altkümenin kesişimi rasyoneldir.

C. Anissimov ve AW, Seifert şu sonuç iyi bilinmektedir sonlu gruplar için: bir alt-grup , H , bir bir sonlu üretilmiş grup G ancak ve ancak tanınabilir lH sahip sonlu indeksi olarak G . Buna karşılık, H rasyoneldir, ancak ve ancak H sonlu olarak üretilirse.

Rasyonel ilişkiler ve rasyonel fonksiyonlar

Bir ikili ilişki monoidler arasında M ve N a, mantıksal bir bağlantı bir alt kümesi olarak ilişkinin grafik, eğer M x N ürün Monoid rasyonel bir kümesidir. Gelen bir fonksiyon M için N a, rasyonel fonksiyonu fonksiyonu grafiği rasyonel grubu ise.

Ayrıca bakınız

• rasyonel seri
• tanınabilir küme
• rasyonel monoid

Referanslar

• Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Bölüm 7: Otomatlar". Ayrık Cebirsel Yöntemler . Berlin/Boston: Walter de Gruyther GmbH. ISBN'si 978-3-11-041332-8.
• Jean-Éric Pin , Otomata Teorisinin Matematiksel Temelleri , Bölüm IV: Tanınabilir ve Rasyonel Kümeler
• Samuel Eilenberg ve MP Schützenberger , Değişmeli Monoidlerde Rasyonel Kümeler , Journal of Algebra, 1969.

daha fazla okuma

• Sakarovitch, Jacques (2009). Otomat teorisinin unsurları . Fransızcadan Reuben Thomas tarafından çevrilmiştir. Cambridge: Cambridge University Press. Bölüm II: Cebirin gücü. ISBN'si 978-0-521-84425-3. Zbl  1188.68177 .