Automata (otomat) Dersinin önemli konularından
birisi olan regular expressions kavramı, tanımlı olan dilde
üretilebilecek olan ifadelerin gösterim biçimidir.
Regular
expressions, constantlardan (sabitler) ve operatörlerden (operators)
oluşan kelimeler kümesi ve bu kelimeler kümesi üzerinde tanımlı
işlemlerdir. Sonlu bir alfabede Σ ‘de aşağıdaki sabitler ( constant )
tanımlıdır.
* (boş küme) ∅ kümenin boş olduğunu gösterir ve ∅ sembolü ile gösterilir
* (boş kelime) ε , {ε} kümesi şeklinde gösterilir
* (değişmez (literal) harf (charachter) ) dil kümesi Σ için {a} kümesi “a” harfini içerir.
Yukarıdaki bu dil için tanımlı işlemler aşağıda verilmiştir:
* ( üleştirme (concatenation) ) RS gösterimi { αβ | α, R için ve β, S için} kümesi şeklinde ifade edilir. Örneğin {“ab”, “c”}{“d”, “ef”} = {“abd”, “abef”, “cd”, “cef”}.
* ( alternation (değişim veya seçim) ) R|S gösteirmi R S lerin birleşim kümesini ifade eder.
* (Kleene star) R*
şeklinde ifade edilir ve R kümesindeki bütün concatenation (üleştirme)
ihtimallerinin oluşturduğu kümeye denilir. Bu kümeye ε dahildir.
Örneğin, {“ab”, “c”}* = {ε, “ab”, “c”, “abab”, “abc”, “cab”, “cc”,
“ababab”, … }.
Bazı kitaplarda | sembolü yerine + V veya U sembolleri de kullanılabilir.
Örnekler:
* a|b* -> {ε, a, b, bb, bbb, …}
* (a|b)* gösterimi , a ve b sembollerinden oluşabilecek bütün kelimeleri ifade eder.
* b*(ab*)* yukarıdaki örnek ile aynı sonucu verir
* ab*(c|ε)
gösterimi, a kelimesi ile başlayan, ve sıfır veya istenilen miktarda b
içeren son olarak da ister c ister ε ile biten kelimeleri ifade eder.
* (aa|ab(bb)*ba)*(b|ab(bb)*a)(a(bb)*a|(b|a(bb)*ba)(aa|ab(bb)*ba)*(b|ab(bb)*a))*
gösterimi, a ve blerden oluşan ve çift sayıda a veya tek sayıda b içeren kelimeleri ifade eder.
1.(ab)* ={εε, ab,…}. bu ifadede “abab” olmaz tüm a’lar b’lerden önce gelmeli demişiz. tüm a’ların b’lerden önce gelmesi arada | (OR) olmamasından dolayı bu “AND” işlemidir. ve a’ların öncelikli olması AND kuralından mı geliyor?
2.(ab*)* = ? (slaytınızda bu ifade geçiyor. bunun eşiti nedir bulamadım.
Bu bahsettiğinizi nerede demişim? Ders sunumuna ve yukarıdaki konu anlatımında böyle bir ifade yok. Farklı ve benim bilmediğim bir yerde mi geçiyor?
Bu yorumunuzdaki ifade hatalı
(ab)* gösterimi, istenildiği kadar ab tekrarını ifade der.
(ab)* = {ε,ab,abab,ababab,…} şeklindeki kümedir ve “abab” ifadesi elbette bu düzenli ifade tarafından içerilir. Bu ifadeden “tüm a’ların b’lerden önce gelmesi” gibi bir yorum yapılamaz.
2. sorunuz için, sanırım slaytta geçenleri buraya yanlış almışsınız. Bahsettiğiniz ifade yanlış anlamadıysam:
(a|b)* = b*(ab*)* olacak. Bu iki ifade birbirine eşittir denilmiş slaytta.
başarılar
Merhaba 0 ve 1 iceren düzenli ifadelerde tek sayıda 0 olma durumunu nasıl ifade edebilirim
merabalar hocam
((bIa)*a)* ve (bIa)*
bu yukaridaki iki farkli ifade ayni dilde yazilabilirmi? Neden?
ikinci ifadeyi mantik olarak anladim ama ilk ifadenin bana demek istedigini anlamadim.
aynı dil ile neyi kastediyorsunuz? iki ifade birbirinden farklıdır. Örneğin ikinci ifadede sadece b üretilebilirken ilk ifadede üretilemez (veya kabul edilmez).
ayni dil ile kastim ayni kelimeler üretilebiliyor mu?
örnegin ilk ((b|a)*a)* ifadesinin icindeki ifadede (b|a)* ifadesini “b” olarak kabul edecek olursak hemen ardindan “a” kelimesini de yazmak zorundayim. Ve sadece “b” sonucunu elde edemiyorum.
Yani ifademizin karsiligi herzaman “a” ile bitmek zoruna oldugu icin “bb” ya da “bbb” gibi bir sonuc hic bir sekilde elde edemem.
Kiymetli zamaninizi bana ayirdiginiz icin tesekkür ederim.
ayni dil ile kastim ayni kelimeler üretilebiliyor mu?
örnegin ilk ((b|a)*a)* ifadesinin icindeki ifadede (b|a)* ifadesini “b” olarak kabul edecek olursak hemen ardindan “a” kelimesini de yazmak zorundayim. Ve sadece “b” sonucunu elde edemiyorum.
Yani ifademizin karsiligi herzaman “a” ile bitmek zoruna oldugu icin “bb” ya da “bbb” gibi bir sonuc hic bir sekilde elde edemem.
Kiymetli zamaninizi bana ayirdiginiz icin tesekkür ederim.