Kleene yıldızı - Kleene star

İçinde matematiksel mantık ve bilgisayar Bilimi, Kleene yıldızı (veya Kleene operatörü veya Kleene kapatma) bir tekli işlem ya açık setleri nın-nin Teller veya sembol veya karakter kümeleri üzerinde. Matematikte daha yaygın olarak serbest monoid inşaat. Kleene yıldızının bir sete uygulanması V olarak yazılmıştır V^*. Yaygın olarak kullanılır düzenli ifadeler tarafından tanıtıldığı bağlam budur Stephen Kleene belirli karakterize etmek Otomata, burada "sıfır veya daha fazla" anlamına gelir.

Eğer V bir dizi dizedir, o zaman V^* en küçük olarak tanımlanır süperset nın-nin V içeren boş dize ε ve kapalı altında dize birleştirme işlemi.
Eğer V bir dizi sembol veya karakter ise V^* içindeki sembollerin üzerindeki tüm dizelerin kümesidir V, boş dize including dahil.

Set V^* aynı zamanda rastgele elemanlarının birleştirilmesiyle üretilebilen sonlu uzunlukta dizeler kümesi olarak da tanımlanabilir. V, aynı öğenin birden çok kez kullanılmasına izin verir. Eğer V ya boş küme ∅ veya tekli set {ε}, sonra V^* = {ε}; Eğer V herhangi biri Sınırlı set veya sayılabilir sonsuz küme, sonra V^* sayılabilir sonsuz bir kümedir.^[1] Sonuç olarak, her biri resmi dil sonlu veya sayılabilir şekilde sonsuz bir alfabe üzerinden sayılabilir.

Operatörler kullanılır kuralları yeniden yaz için üretken gramerler.

Tanım ve gösterim

Bir set verildi Vtanımlamak

V⁰ = {ε} (yalnızca boş dizeden oluşan dil),

V¹ = V

ve kümeyi yinelemeli olarak tanımlayın

V^ben+1 = { wv : w ∈ V^ben ve v ∈ V } her biri içinben > 0.

Eğer V resmi bir dil ise V^ben, bensetin gücü V, kısaltmasıdır birleştirme set V kendisiyle ben zamanlar. Yani, V^ben hepsinin kümesi olarak anlaşılabilir Teller bu birleştirilmiş olarak temsil edilebilir ben dizelerV.

Kleene star on'un tanımı V dır-dir^[2]

{displaystyle V ^ {*} = igcup _ {igeq 0} V ^ {i} = V ^ {0} fincan V ^ {1} fincan V ^ {2} fincan V ^ {3} fincan V ^ {4} fincan cdot'lar.}

Bu, Kleene yıldız operatörünün bir etkisiz tekli operatör: (V^*)^* = V^* herhangi bir set için V dizelerin veya karakterlerin (V^*)^ben = V^* her biri için ben≥1.

Kleene artı

Bazılarında resmi dil çalışmalar, (ör. AFL teorisi ) Kleene yıldız operasyonunun bir varyasyonu olarak adlandırılan Kleene artı kullanıldı. Kleene plus, V⁰ Yukarıdaki birlikteki terim. Başka bir deyişle, Kleene plus V dır-dir

{displaystyle V ^ {+} = igcup _ {igeq 1} V ^ {i} = V ^ {1} fincan V ^ {2} fincan V ^ {3} fincan cdot.}

veya

{displaystyle V ^ {*} setminus V ^ {0} = V ^ {+} = V ^ {*} V}

^[3]

Örnekler

Dizi kümesine uygulanan Kleene yıldızı örneği:

{"ABC"}^* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc "," ccab "," ccc ", ...}.

Karakter kümesine uygulanan Kleene plus örneği:

{"a", "b", "c"}⁺ = {"a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

Kleene yıldızı aynı karakter setine uygulandı:

{"a", "b", "c"}^* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc "," aaa "," aab ", ...}.

Boş kümeye uygulanan Kleene yıldızı örneği:

∅^* = {ε}.

Boş sete uygulanan Kleene plus örneği:

∅⁺ = ∅ ∅^* = { } = ∅,

burada birleştirme bir ilişkisel ve değişmez ürün, bu mülklerin paylaşılması Kartezyen ürün setleri.

Boş dizeyi içeren tekli sete uygulanan Kleene plus ve Kleene yıldızı örneği:

V = {ε} ise, o zaman da V^ben = her biri için {ε} bendolayısıyla V^* = V⁺ = {ε}.

Genelleme

Dizeler bir monoid ikili işlem olarak bitiştirme ve element kimlik öğesi. Kleene yıldızı herhangi bir monoid için tanımlanmıştır, sadece sicimler için değil.M, ⋅) bir monoid olmak ve S ⊆ M. Sonra S^* en küçük submonoid M kapsamak S; yani, S^* nötr unsurunu içerir M, set Sve öyle ki eğer x,y ∈ S^*, sonra x⋅y ∈ S^*.

Ayrıca, Kleene yıldızı, * operasyonunu (ve birleşmeyi) ekleyerek genelleştirilir. cebirsel yapı kendisi nosyonuyla yıldız yarı devrini tamamla.^[4]

Ayrıca bakınız

Referanslar

^ Nayuki Minase (10 Mayıs 2011). "Sayılabilir setler ve Kleene yıldızı". Nayuki Projesi. Alındı 11 Ocak 2012.
^ Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Matematiksel Mantık (2. baskı). New York: Springer. s. 656. ISBN 0-387-94258-0. Kleene kapatma L^* nın-nin L olarak tanımlandı ${displaystyle kenar kümesi {} {_ {i = 0} ^ {infty}} igcup L ^ {i}}$ .
^ Doğru denklem geçerli çünkü her unsur V⁺ ya bir öğeden oluşmalıdır V ve sonlu çok sayıda boş olmayan terim V veya sadece bir unsurdur V (nerede V kendisi alınarak geri alınır V ε ile birleştirilir).
^ Droste, M .; Kuich, W. (2009). "Bölüm 1: Yarı Halkalar ve Biçimsel Güç Serileri". Ağırlıklı Otomata El Kitabı. Teorik Bilgisayar Biliminde Monograflar. Springer. s.9. doi:10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.

daha fazla okuma

Hopcroft, John E.; Ullman, Jeffrey D. (1979). Otomata Teorisi, Dilleri ve Hesaplamaya Giriş (1. baskı). Addison-Wesley.

[1] Nayuki Minase (10 Mayıs 2011). "Sayılabilir setler ve Kleene yıldızı". Nayuki Projesi. Alındı 11 Ocak 2012.

[2] Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Matematiksel Mantık (2. baskı). New York: Springer. s. 656. ISBN 0-387-94258-0. Kleene kapatma L^* nın-nin L olarak tanımlandı ${displaystyle kenar kümesi {} {_ {i = 0} ^ {infty}} igcup L ^ {i}}$ .

[3] Doğru denklem geçerli çünkü her unsur V⁺ ya bir öğeden oluşmalıdır V ve sonlu çok sayıda boş olmayan terim V veya sadece bir unsurdur V (nerede V kendisi alınarak geri alınır V ε ile birleştirilir).

[droste-4] Droste, M .; Kuich, W. (2009). "Bölüm 1: Yarı Halkalar ve Biçimsel Güç Serileri". Ağırlıklı Otomata El Kitabı. Teorik Bilgisayar Biliminde Monograflar. Springer. s.9. doi:10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.

[1]

[2]

[3]

[4]