Düzenli İfadeler

Düzenli ifade, bir sözcük kümesini tanımlamamızı sağlayan metin dizisidir. Düzenli ifadeleri sonlu otomatı tanımlamanın basit bir yolu olarak da düşünebiliriz.

Düzenli İfade Nedir

Aritmetikte · ve + gibi simgeleri kullanarak örneğin (2 + 3) · 4 gibi bir ifade oluştururuz. Bu ifadeyi hesaplayınca bir sayı elde ederiz. Düzenli ifade ise karakterlerden ve birkaç özel simgeden oluşan bir dizidir, örneğin a(x ∪ y). Bu ifadenin değeri bir (biçimsel) dildir. (2 + 3) · 4 ifadesinin sonucu 20 sayısıdır, a(x ∪ y) düzenli ifadesinin sonucu ise “ax”, “ay” sözcüklerinden oluşan iki elemanlı bir kümedir.

Önceki a(x ∪ y) düzenli ifadesini nasıl hesaplardık? Her harf aslında o harfi içeren tek elemanlı bir kümenin kısaltmasıdır, gizli çarpma ise sözcüklerin birleştirilmesidir. Düzenli ifadeyi “tam haliyle” şöyle yazabiliriz:

$$\left\{a\right\}\circ (\left\{x\right\}\cup \left\{y\right\})$$

Sonra şöyle hesaplarız: {x} ∪ {y} birleşimi bize {x,y} dilini verir. {a} ve {x,y} dillerini birleştirince {ax, ay} dilini elde ederiz.

Düzenli ifadeler programlamada çok sık kullanılır ve çoğu programlama dilinde bir biçimde uygulanmıştır. Örneğin kullanıcının girdiği metnin belirli ölçütleri sağlayıp sağlamadığını denetlemek için (geçerli bir e-posta mı, geçerli bir tarih mi vb.) ya da metinleri değiştirmek için (örneğin metindeki tüm URL’leri tıklanabilir bağlantılarla değiştirmek isteyebiliriz) kullanılırlar.

Gerçek uygulamalardaki düzenli ifadeler çoğunlukla burada anlatılanlardan daha güçlüdür ve biraz farklı, ama özellikle daha karmaşık bir sözdizimi kullanır.

Düzenli İfadenin Tanımı

Düzenli ifadeyi bir Σ alfabesi üzerinde tanımlayacağız. Düzenli ifade şunlardan biridir:

1. a, burada a ∈ Σ. Yani alfabenin tek bir karakteri de düzenli ifadedir.

2. ϵ: boş sözcük. Programlamada boş tırnak, yani “” ile de yazılır.

3. ∅: düzenli ifade boş dili de tanımlayabilmelidir, bu yüzden boş dil de düzenli ifadedir.

4. (R₁ ∪ R₂), burada R₁, R₂ düzenli ifadelerdir.

5. (R₁ ∘ R₂), burada R₁, R₂ düzenli ifadelerdir.

6. (R^∗), burada R düzenli bir ifadedir.

7. maddedeki ∪ simgesi yerine dikey çizgi | de kullanabiliriz. ∘ simgesi yerine ise hiçbir şey yazmak zorunda değiliz. Çarpma simgesini, yani orta noktayı · çoğunlukla doğrudan yazmadığımız gibi birleştirme simgesi ∘ da çoğunlukla yazılmaz. Bu yüzden şu düzenli ifadeler aynıdır: a ∘ (b ∪ c) ve a(b|c).

Bu işleçler ne anlama gelir?

• ∪ veya | dillerin birleşimini gösterir.
• ∘ dillerin birleştirilmesini gösterir.
• ^∗ dilin Kleene kapanışını gösterir.

Örnekler:

• a basit {a} dilini gösterir.
• a|b iki sözcükten oluşan {a, b} dilini gösterir.
• a ∘ b {ab} dilini gösterir.
• a(b|c)d {abd, acd} dilini gösterir.
• a(b^∗) “a” harfiyle başlayan ve ardından istenen sayıda “b” harfi gelen tüm sözcüklerin dilini gösterir.
• (ab)^∗ {ϵ, ab, abab, ababab, …} sözcüklerinin dilini gösterir.
• 0^∗10^∗ tam olarak bir tane 1 içeren tüm ikili sözcüklerin dilini gösterir. (Bu ifadeyi daha doğru biçimde (0^∗)1(0^∗) diye yazabileceğimize dikkat et, ama gösterim parantezsiz de okunaklıysa parantezleri atlayabiliriz.)
• Σ^∗1Σ^∗ en az bir tane 1 içeren tüm sözcüklerin dilini gösterir.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ tüm pozitif tam sayıların dilini gösterir.

Şimdi düzenli ifadeler ile sonlu otomatlar arasındaki denkliği göstereceğiz. Sonucu R dili olan her düzenli ifade için L(A) = R olacak şekilde bir A sonlu otomatı vardır ve bunun tersi de doğrudur.