Düzenli İfadelerle Üçün Katları
Türkiye Cumhuriyeti Kimlik Numaralarını üretmek ve geçerli mi değil mi diye kontrol etmek için TurkishIdQt isimli basit bir uygulama yazdıktan sonra doğrulama işleminin bir düzenli ifadeyle yapılıp yapılamayacağını merak etmeye başladım.
Kısa bir araştırmayla aradığım şeyin çok basit bir hali olan
Türkiye Cumhuriyeti Kimlik Numaralarının geçerliğini kontrol etmek için toplama, çıkarma, çarpma ve mod alma gibi matematiksel işlemler yapılması gerekiyor. Bunların hepsinin düzenli ifadelerle gerçekleştirilip gerçekleştirilemeyeceğini bilmiyorum ama konuyla ilgili yeni bir şeyler öğrenmek için denk geldiğim kaynaklara göz atıyorum.
Hem daha iyi öğrenebilmek hem de sizlerin de haberdar olmasını sağlamak için ilginç şeylerle karşılaşırsam konu hakkında yazmaya çalışacağım şimdi olduğu gibi.
3'ün katlarıyla eşleşen durum makinesini kurarak işe başlayalım. Bir sayının, sadece rakamlarının toplamı 3'ün bir katıysa 3'e bölünebileceğini biliyoruz.
Durum makinesi, girişi işleyecek ve rakamların toplamını izleyecektir. Yalnızca toplamın mod 3 işlemine tabi tutulmasına ihtiyacımız var. Bu yüzden 3 durumlu epey basit bir durum makinemiz olacak: durum A (başlangıç durumu), durum B (1 ile sonlanma), durum C (2 ile sonlanma).
A durumundayken "0", "3", "6" veya "9" alırsak A durumunda kalmaya devam ederiz, "1", "4" veya "7" alırsak B durumuna hareket ederiz, "2", "5" veya "8" alırsak C durumuna geçeriz:
B durumundayken de benzer kurallar geçerlidir:
Ve son olarak, işte durum makinesinin son hali:
Burada belki B ve C durumundan diğer durumlara neye göre hareket edildiği anlaşılmamış olabilir. B durumuna bir kalan oluştuğu için gelmiştik, bu durumdayken hiç kalan oluşmazsa orada kalmaya devam ediyoruz, iki kalan oluşursa, elimizdeki bir kalanla birlikte toplamda üç kalan oluştuğu için A durumuna geçiyoruz, bir kalan oluştuğundaysa toplamda iki kalan olacağından C durumuna gidiyoruz. C durumundaki hareketler de aynı bu mantıkla gerçekleşiyor.
A = ∅ | A[0369] | B[258] | C[147]
B = A[147] | B[0369] | C[258]
C = A[258] | B[147] | C[0369]
∅ başlangıç durumunu temsil ediyor. Sürekli [0369], [147] ve [258] yazmak zor olacağı için bunların yerine sırasıyla sadece 0, 1 ve 2 yazalım:
A = ∅ | A0 | B2 | C1
B = A1 | B0 | C2
C = A2 | B1 | C0
Şimdiki amacımız A'nın formülünü bulmak için B ve C'yi yerine koymak. X = Xw | Y | Z gibi özyinelemeli kurallar, X = Yw* | Zw* olur ve X = (Y | Z) w* olarak da yazılabilir:
A = ( ∅ | B2 | C1 ) 0*
B = ( A1 | C2 ) 0*
C = ( A2 | B1 ) 0*
C'yi yerine koymak kolay olacaktır:
A = ( ∅ | B2 | ( A2 | B1 ) 0* 1 ) 0*
B = (A1 | ( A2 | B1 ) 0* 2 ) 0*
Bu işlemi tekrarlıyoruz:
A = 0* | B2 0* | ( A2 | B1 ) 0* 1 0*
B = A1 0* | ( A2 | B1 ) 0* 2 0*
A = 0* | B2 0* | A2 0* 1 0* | B1 0* 1 0*
B = A1 0* | A2 0* 2 0* | B1 0* 2 0*
A = ( 0* | B2 0* | B1 0* 1 0* ) ( 2 0* 1 0* )*
B = ( A1 0* | A2 0* 2 0* ) ( 1 0* 2 0* )*
Şimdi B'yi yerine koyabiliriz:
A = (
0* |
( A1 0* | A2 0* 2 0* ) (1 0* 2 0* )* 2 0* |
( A1 0* | A2 0* 2 0* ) (1 0* 2 0* )* 1 0* 1 0*
) (2 0* 1 0* )*
A = 0* ( 2 0* 1 0* )* |
A1 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
A2 0* 2 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
A1 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )* |
A2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )*
Bu noktada, X = a (b | c)* olarak ifade edilebilecek X = a | Xb | Xc gibi bir şeyimiz var:
A = 0* ( 2 0* 1 0* )* (
1 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
2 0* 2 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
1 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )* |
2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )*
)*
Bir çözüm bulduk, bu kural bir düzenli ifadeye dönüştürülebilir! Bununla birlikte, biraz daha sadeleştirme yapabiliriz. a* ( b a* )*, ( a | b )* olur:
A = 0* (
2 0* 1 0* |
1 0* ( 1 0* 2 0* )* 2 0* |
2 0* 2 0* ( 1 0* 2 0* )* 2 0* |
1 0* ( 1 0* 2 0* )* 1 0* 1 0* |
2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0*
)*
Aynı kuralı tekrar kullanırsak:
A = (
0* |
2 0* 1 |
1 ( 0 | 1 0* 2 )* 2 |
2 0* 2 ( 0 | 1 0* 2 )* 2 |
1 ( 0 | 1 0* 2 )* 1 0* 1 |
2 0* 2 ( 0 | 1 0* 2 )* 1 0* 1
)*
Ayrıca yukarıdakinden daha basit bir çözüm de varmış:
Konunun daha iyi anlaşılabilmesi için söyleyeceğiniz bir şeyler varsa veya düzenli ifadelerle ilgili bunun gibi harika özellikler biliyorsanız yorum olarak belirtmekten çekinmeyin.
Kısa bir araştırmayla aradığım şeyin çok basit bir hali olan
^[1-9]{1}[0-9]{10}$ifadesini buldum ama bu yeterli gelmeyince araştırmaya devam ettim.
Türkiye Cumhuriyeti Kimlik Numaralarının geçerliğini kontrol etmek için toplama, çıkarma, çarpma ve mod alma gibi matematiksel işlemler yapılması gerekiyor. Bunların hepsinin düzenli ifadelerle gerçekleştirilip gerçekleştirilemeyeceğini bilmiyorum ama konuyla ilgili yeni bir şeyler öğrenmek için denk geldiğim kaynaklara göz atıyorum.
Hem daha iyi öğrenebilmek hem de sizlerin de haberdar olmasını sağlamak için ilginç şeylerle karşılaşırsam konu hakkında yazmaya çalışacağım şimdi olduğu gibi.
Merak
Yalnızca üçün katlarıyla eşleşen düzenli bir ifade yazabilir misiniz? Yani "3", "03", "24", "1122" ile eşleşme olması isteniyor ancak "5", "10" veya "20" ile eşleşme olmamalı. Eğer bunun nasıl yapıldığını merak ediyor ve öğrenmek istiyorsanız Alok Menghrajani'nin regular expression to match multiples of 3 yazısının bu Türkçe çevirisini okumaya devam edin:Zor Yol
Çözümü bulmanın zor yolu, doğrudan düzenli ifadeyi yazmaya çalışmaktır. Çözüm için basitçe/^(0|10*2|10*10*1|20*1)+$/(burada 0 aslında [0369], 1 [147] ve 2 [258] değerlerine eşittir) ifadesini yazabileceğinizi düşünebilirsiniz. Ancak, 1122, 2211 veya 222 gibi durumları gözden kaçırmış olacaksınız. Yeni durumları eklemeye devam edebilirsiniz ve sonunda çözüme kavuşursunuz, ancak bu zor olacaktır...
Sonlu Durum Makineleri
Sorunu çözmenin daha kolay bir yolu, düzenli ifadelerin sonlu durum makineleri olarak, sonlu durum makinelerinin de düzenli ifadeler olarak yazılabileceğini anlamayı gerektirir.3'ün katlarıyla eşleşen durum makinesini kurarak işe başlayalım. Bir sayının, sadece rakamlarının toplamı 3'ün bir katıysa 3'e bölünebileceğini biliyoruz.
Durum makinesi, girişi işleyecek ve rakamların toplamını izleyecektir. Yalnızca toplamın mod 3 işlemine tabi tutulmasına ihtiyacımız var. Bu yüzden 3 durumlu epey basit bir durum makinemiz olacak: durum A (başlangıç durumu), durum B (1 ile sonlanma), durum C (2 ile sonlanma).
A durumundayken "0", "3", "6" veya "9" alırsak A durumunda kalmaya devam ederiz, "1", "4" veya "7" alırsak B durumuna hareket ederiz, "2", "5" veya "8" alırsak C durumuna geçeriz:
Dönüşüm
Durum makinesini düzenli ifadeye dönüştürmek için önce bazı denklemleri yazmamız gerekir. Her durum için oraya nasıl gideceğimizi yazıyoruz:A = ∅ | A[0369] | B[258] | C[147]
B = A[147] | B[0369] | C[258]
C = A[258] | B[147] | C[0369]
∅ başlangıç durumunu temsil ediyor. Sürekli [0369], [147] ve [258] yazmak zor olacağı için bunların yerine sırasıyla sadece 0, 1 ve 2 yazalım:
A = ∅ | A0 | B2 | C1
B = A1 | B0 | C2
C = A2 | B1 | C0
Şimdiki amacımız A'nın formülünü bulmak için B ve C'yi yerine koymak. X = Xw | Y | Z gibi özyinelemeli kurallar, X = Yw* | Zw* olur ve X = (Y | Z) w* olarak da yazılabilir:
A = ( ∅ | B2 | C1 ) 0*
B = ( A1 | C2 ) 0*
C = ( A2 | B1 ) 0*
C'yi yerine koymak kolay olacaktır:
A = ( ∅ | B2 | ( A2 | B1 ) 0* 1 ) 0*
B = (A1 | ( A2 | B1 ) 0* 2 ) 0*
Bu işlemi tekrarlıyoruz:
A = 0* | B2 0* | ( A2 | B1 ) 0* 1 0*
B = A1 0* | ( A2 | B1 ) 0* 2 0*
A = 0* | B2 0* | A2 0* 1 0* | B1 0* 1 0*
B = A1 0* | A2 0* 2 0* | B1 0* 2 0*
A = ( 0* | B2 0* | B1 0* 1 0* ) ( 2 0* 1 0* )*
B = ( A1 0* | A2 0* 2 0* ) ( 1 0* 2 0* )*
Şimdi B'yi yerine koyabiliriz:
A = (
0* |
( A1 0* | A2 0* 2 0* ) (1 0* 2 0* )* 2 0* |
( A1 0* | A2 0* 2 0* ) (1 0* 2 0* )* 1 0* 1 0*
) (2 0* 1 0* )*
A = 0* ( 2 0* 1 0* )* |
A1 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
A2 0* 2 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
A1 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )* |
A2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )*
Bu noktada, X = a (b | c)* olarak ifade edilebilecek X = a | Xb | Xc gibi bir şeyimiz var:
A = 0* ( 2 0* 1 0* )* (
1 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
2 0* 2 0* ( 1 0* 2 0* )* 2 0* ( 2 0* 1 0* )* |
1 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )* |
2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0* ( 2 0* 1 0* )*
)*
Bir çözüm bulduk, bu kural bir düzenli ifadeye dönüştürülebilir! Bununla birlikte, biraz daha sadeleştirme yapabiliriz. a* ( b a* )*, ( a | b )* olur:
A = 0* (
2 0* 1 0* |
1 0* ( 1 0* 2 0* )* 2 0* |
2 0* 2 0* ( 1 0* 2 0* )* 2 0* |
1 0* ( 1 0* 2 0* )* 1 0* 1 0* |
2 0* 2 0* ( 1 0* 2 0* )* 1 0* 1 0*
)*
Aynı kuralı tekrar kullanırsak:
A = (
0* |
2 0* 1 |
1 ( 0 | 1 0* 2 )* 2 |
2 0* 2 ( 0 | 1 0* 2 )* 2 |
1 ( 0 | 1 0* 2 )* 1 0* 1 |
2 0* 2 ( 0 | 1 0* 2 )* 1 0* 1
)*
Çözüm
Yukarıdaki kural, başına ^ ve sonuna $ eklenerek bir düzenli ifadeye dönüştürülebilir:/^(0|20*1|1(0|10*2)*2|20*2(0|10*2)*2|1(0|10*2)*10*1|20*2(0|10*2)*10*1)*$/Ayrıca 0'ı [0369] ile, 1'i [147] ile ve 2'yi [258] ile değiştirmemiz gerekir:
/^([0369]|[258][0369]*[147]|[147]([0369]|[147][0369]*[258])*[258]|[258][0369]*[258]([0369]|[147][0369]*[258])*[258]|[147]([0369]|[147][0369]*[258])*[147][0369]*[147]|[258][0369]*[258]([0369]|[147][0369]*[258])*[147][0369]*[147])*$/İnanmıyorsanız bu düzenli ifadeyi RegExr gibi bir sitede kendiniz deneyebilirsiniz.
Ayrıca yukarıdakinden daha basit bir çözüm de varmış:
/^(0|20*1|(1|20*2)(0|10*2)*(2|10*1))*$/
/^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$/
Sonuç
Henüz ben de dönüşüm işlemlerinin tamamını anlamış değilim. Biraz daha araştırma yapıp benzer bir işlemi Türkiye Cumhuriyeti Kimlik Numaraları için uygulamaya çalışırken daha iyi anlarım diye düşünüyorum.Konunun daha iyi anlaşılabilmesi için söyleyeceğiniz bir şeyler varsa veya düzenli ifadelerle ilgili bunun gibi harika özellikler biliyorsanız yorum olarak belirtmekten çekinmeyin.
Eklemeler
- Şuradaki yorumlarda da işe yarar şeyler olabilir.
Yorumlar
Yorum Gönder
sen de yaz yaz yaz buraya yaz bütün sözlerini