BİÇİMSEL DİLLER ve ÖZDEVİNİRLER -3

Görsel OpenAI’nin DALL-E modelinden üretilmiştir.

Merhabalar bu yazımda Biçimsel Diller ve Özdevinirler konusunda kaldığım yerden devam edeceğim.

Düzgün Kümeler(Regular Sets)

Düzgün kümeler, belirli bir kurala göre tanımlanabilen, sonlu bir alfabeden türetilmiş sözcükler kümesidir. Düzgün diller olarak da bilinen bu kümeler, sonlu otomatalar veya düzenli ifadelerle tanımlanabilen dillerden oluşur. Bu kümelerin tüm öğeleri belirli kurallarla türetilmiştir ve bu tür kümelerin tanımlanması için genellikle düzenli deyimler kullanılır.

Örneğin {0, 1} alfabesinde, sonlu bir özdevinir tarafından tanınan aşağıdaki kümeleri tanımlayabiliriz: P5={101,1101,10001}P5​={101,1101,10001} Belirli dizgilerden oluşan, sonlu bir dizgiler kümesi.

• P₀​={101,1101,10001} Belirli dizgilerden oluşan, sonlu bir dizgiler kümesi.
• P₁= İçinde “01” alt dizisini en az bir kere bulunduran dizgiler kümesi.
• P₂= Son iki simgesi “00” olan tüm dizgiler kümesi.

Bir küme verildiğinde, bu kümenin düzgün bir küme olup/olmadığı, bu kümeyi tanıyan sonlu bir özdevinirin bulunup/bulunmaması tarafından belirlenir. Eğer kümeyi tanıyan en az bir sonlu özdevinir varsa, bu küme düzgün bir kümedir. Eğer verilen kümeyi tanıyan hiçbir sonlu özdevinir yoksa, bu küme düzgün bir küme değildir.

Yukarıda tanımlananP₀​, P₁ ve P₂ kümeleri düzgün kümelerdir. Çünkü bu kümelerin her birini tanıyan en az bir sonlu özdevinir oluşturulabilir.

• V₀​= İçinde eşit sayıda 0 ve 1 bulunan dizgiler kümesi

V₀ kümesi düzgün bir küme değildir. Çünkü bu kümeleri tanıyan sonlu özdevinirler oluşturulamaz. V₀’ı tanıyacak bir makinenin, dizgiyi taraması ve sürekli olarak, o ana kadar rastlanan 0’larla 1’lerin sayılarının farkını saklaması gerekir. Eğer dizginin sonunda, 0’larla 1’lerin sayılarının farkı sıfırsa, dizgi makine tarafından tanınacaktır. Ancak 0’larla 1’lerin sayılarının farkının bir üst sınırı yoktur. Bu fark, düşünülebilecek tüm sonlu sayılardan daha büyük olabilir. Bu nedenle de sonlu özdevinir olamaz.

Düzgün Deyimler (Regular Expressions)

Düzgün deyimler, düzenli dillerin tanımlanmasında kullanılan sembol dizileridir. Düzgün deyimler, belirli bir dilin yapısını tarif etmek için kullanılan sembollerden ve operatörlerden oluşur. Her düzgün deyim, belirli bir alfabedeki simgelerden oluşturulabilecek dizgilerin bir altkümesini tanımlar.

Tanım: { a, b, c, … } alfabesindeki düzgün deyimler özyineli olarak aşağıdaki gibi tanımlanır: 1- Alfabedeki her simge düzgün bir deyimdir. a = {a}, b = {b}, …

2- λ ve ∅ birer düzgün deyimdir. λ = {λ} , ∅ = { }

3-Eğer P ve Q düzgün deyimse: P + Q , PQ, P da düzgün deyimdir. P + Q = P∪Q , PQ = {p∩q | p∈P , q∈Q} P = λ+ P + PP + PPP + PPPP + …

Bu kuralların sonlu sayıda uygulanması ile oluşturulan deyimler düzgün deyimlerdir.

Örnek: Aşağıda {a, b, c , d} alfabesinden oluşturulmuş düzgün deyim örnekleri ve bunlara karşı gelen kümeler görülmektedir.

Bu yazımda, Düzgün Kümeler (Regular Sets) ve Düzgün Deyimler (Regular Expressions) konularına odaklandım. İlk olarak, düzgün kümelerin tanımını yaparak, bu kümelerin özelliklerini ve nasıl çalıştıklarını inceledim. Daha sonra, düzgün deyimlerin tanımını ele alarak, bu deyimlerin nasıl kullanıldığını ve düzenli dillerin ifade edilmesindeki rolünü inceledim. Son olarak, düzgün kümeler ve düzgün deyimler arasındaki ilişkiye odaklanarak, her iki yapının nasıl birbirini tamamladığını ve birlikte nasıl çalıştığını açıklamaya çalıştım.

Umarım faydalı bir yazı olmuştur, sonraki yazımda görüşmek üzere.

https://samedsonkaya.com/