Biçimsel Diller Ve Otomata Teorisi -1

BİRİNCİ BÖLÜM

Herkese yeniden merhaba!

Bilgisayar mühendisliği bölümünün en zor dersi olarak nam yapan, dönem uzatmalara sebep olan ve dersi dinlerken bile kafa yakan mükemmel bir dersi kaleme alarak yazı yazmaya geri dönüyorum!

Neredeyse bu konuda yazılmış her kitabı tarayarak ve edindiğim tüm bilgilere kendi yorumlarımı katarak en kolay anlaşılabilir şekilde naçizane anlatmaya çalışacağım yazı serisi olan Biçimsel Diller ve Otomata Serisi umarım hoşunuza gider.

Okul hayatımın istisnasız en zevk alarak dinlediğim dersi için öğretmenim Serkan Öztürk’e ve dersi birlikte çalışırken çok zevk aldığım arkadaşım Mustafa Etcil’e çok teşekkürler!

Yazımızı “Otomata teorisi nedir?” sorusu ile başlatalım. En basit tabir ile Otomata Teorisi (Automata Theory) teorik bilgisayar biliminde soyut makineleri ve bu makineleri kullanarak hesaplama problemlerinin çözülebilmesini araştıran daldır. Bu soyut makineleri ise otomat olarak adlandırırız.

Otomata Teorisi birçok sınıflandırılmaya ayrılmaktadır. Bu sınıflardan bahsetmeden önce Otomata teorisinin yakından ilgilendiği Biçimsel Dil Kuramı hakkında bilgi sahibi olmalıyız.

this image is taken from Boris Lavrov

Biçimsel diller bilgisayar bilimlerinde, mantıkta ve dil bilim çalışmalarında kullanılan bir dil ailesidir. Dilde bulunan bütün ögeler ve dilin ulaşabileceği sınırlar belirli kurallar dahilinde tanımlanabiliyorsa bu dillere biçimsel dil ismini verebiliriz.

Bu anlamda bilgisayar bilimlerinde bulunan bütün programlama dillerini bu ailede düşünmek mümkündür ve sıfırdan bir programlama dili geliştirmek isteyen bir bilgisayar programcısının ilk öğrenmesi gereken konulardan birisi olduğunu söylememiz de yanlış olmaz.

Biçimsel dili tanımlamak için dilin en küçük yapısı olan alfabe, kelime kavramlarını öğrenerek başlamamız gerekir. Bir dilde kullanılan sembollere harf denilir ve harflerin listesine de alfabe (alphabet) veya bir diğer ismi ile abece denilir.

‘∑’ dilin en küçük yapı taşı olan alfabeyi temsil etmektedir.

∑ = {x}

Örneğin yukarıdaki ∑ alfabesi “x” harfini içermektedir. Bu harf dışındaki hiçbir sembol bu alfabede tanımlı değildir.

L₁= {λ,x,xx,xxx,xxxx,…} , L₁= {xⁿ for n = 1 2 3 … }

L₁ dilinde yer alan terimler ise kelimelerdir. Harf içermeme durumu ise null string ‘λ ‘ ile gösterilir.

İşlemlerimizi örnek ∑ = {a,b} alfabesi üzerinde gösterelim;

▪️Lenght ile bir kelimenin uzunluğunu ölçeriz;

lenght(ab) =2 , lenght(λ)=0

▪️Reverse ile verilen kelimenin tersini yazmamızı sağlar;

reverse(ab)=ba

▪️Kleene Star ‘*’ ile λ dahil, alfabedeki tüm karakterlerin mümkün olan tüm birleşimlerini elde eder. Yani biz bir alfabenin önüne( yıldızı (*)) koyduğumuz zaman o alfabede istediği kadar istediği kombinasyonu yapabilir ya da yapmayabilir.

Σ*={λ,a,b,ab,ba,aa,bb,aaa,...} “Karakter sayısı sonsuzdur.” (ab)*≠a*b*

▪️ + (Plus) En az bir kere o karakterden gelmesi anlamında gelir. Σ^+ = Σ*-λ

Σ+={a,b,ab,ba,aa,bb,aaa,…}

▪️Recursive Definitions (Öz yinelemeli Tanımlamalar) En genel anlamıyla bir yapının (kendi kendine) yinelenmesidir.

Birden çok şekilde bulunabildiği için nondeterministictir.

▪️Regular Expressions (REx) tanımlı olan dilde üretilebilecek olan ifadelerin gösterim biçimidir.

Alfabemizin a ve b harflerinden oluştuğunu düşünelim ve bu harflerden oluşan çeşitli diller tanımlayalım.

1. S=(a+b) ; bu dilin kabul ettiği kelimeler yalnızca a veya b’dir. => {a,b}
2. S= (a+b)(a+b) = (a+b)² ; bu dilin kabul ettiği kelimeler ; {aa,ab,ba,bb} yani a ve b harfleri kullanılarak yazılabilecek 2 harfli stringlerdir.
3. S=(a+b)(a+b)(a+b) = (a+b)³ ; dilinin kabul ettiği kelimeler ise tahmin edilebileceği üzere a ve b harfleriyle yazılabilecek 3 harfli tüm stringlerdir.

Peki (a+b)* dili ne tür kelimeleri kabul eder?
(a+b)^n = (a+b)(a+b)(a+b) …n kez…. (a+b) olduğuna göre , ve *(kleene star) n değerinin 0'dan sonsuza kadar bütün değerleri alabileceğini ifade ettiğine göre ;

(a+b)* ifadesi , a ve b harfleriyle oluşturulabilecek tüm kombinasyonları (sonsuz sayıda) kabul etmektedir.

Çalışma notlarım -1

Birkaç rex örneği ile konumuzu pekiştirelim;

Çalışma Notlarım -2

Biraz daha zorlaştıralım 🚀

Çalışma Notlarım -3

Birinci Bölümü bu bilgilerle sonlandırıyorum. Çok yakında yeni bölümlerle serimize devam edeceğim. Umarım beğenirsiniz. Bir sonraki yazımda görüşmek üzere. 👽

Beni Linkedin ve Twitter hesaplarımdan da takip edebilirsiniz!🐞

Kaynaklar

1-INTRODUCTION TO COMPUTER THEORY -Daniel I. A. Cohen Hunter College City University of New York

2-http://bilgisayarkavramlari.sadievrenseker.com/category/automata-otomatlar/page/2/