BİÇİMSEL DİLLER VE OTOMATA — Giriş #1
Merhaba arkadaşlar,
Otomata ile ilgili yeni bir seri başlatıyorum umarım herkes için faydalı olur.
Giriş
Bilgisayar mühendisliği bölümünde gerçekten üst seviye derslerden birisidir. Genellikle 2–3 üniversitenin ders planını incelediğimde 4. Sınıfta yer alan bu ders temel dil yapıları ile ilgili bir altyapı oluşturmaktadır.
Otamata Teorisi (Automata Theory) teorik olarak bilgisayar bilimlerindeki soyut makineleri kullnarak hesaplama problemlerinin çözülmesini araştıran daldır.
Sonlu Otamatlar (Finite Automata)
Örnek olarak 5 TL ve 10 TL’lik paraları kabul eden ve fiyatı 15 tl otomat olsun. Paraları makineye girip bir tuşa bastığınızda. Makine ya ürünü veriyor yada reddedip attığımız paraları iade ediyor.
Otomatın şemasın dada görüldüğü gibi eğer state 15 geldiğinde otomatı sonlandırmamız gerekiyor(kabul durumu) başka bir durumda isteğimiz (request) kabul edilmiyor.
Teknik Terimler
Otamata teorisinin bir alt dalıda biçimsel dillerdir.Biçimsel diller bilgisayar bilimlerinde yada matematikteki mantıkta kullandığımız dillerdir.Genel olarak dilde bulunan bütün öğeler ve dilin ulaşabileceği sınırlar belirli kurallar dahilinde tanımlanabiliyorsa bu dillere biçimsel dil ismini verebiliriz.
Alfabe, sonlu bir semboller kümesidir.
Dizgi, Alfabe üzerinde tanımlı sembol dizisi (Örnek olarak “kelime)
Epsilon, Uzunluğu sıfır olan dizgi
Dil, Dizgiler kümesi
Yukarıdaki görselde görüldüğü üzere ;
∑={0,1} alfabemizi temsil eder.
Otamatın state’leri:q1,q2,q3,q4,q5
Başlangıç state:q1
Kabul State:q3,q4
Oklar geçişleri belirtir. Burada bir tane olması her durum ve her sembol için yalnızca bir geçişin olduğunu belirtir.
Otamata 010001 girişi verilirse otamat çıkış olarak ya onay yada ret cevabı döner.
Örnek olarak 0, 01, 11, 10, 111, 10000, 011, 111111, etc. stringleri verildiğinde algoritma çıkış olarak onay döner.
Örnek olarak 1, 00, 010, 0000, 010101, 0001, etc. verilirse otamat çıkış olarak red cevabı döner.
Burada unutulmaması gereken birkaç husus vardır. Kabul etme durumu olmayan tüm durumların ret durumları olduğuna dikkat edin. Ayrıca q5’e girdiğimizde çıkamıyoruz ve bu bir red durumu, bu yüzden buna tuzak durumu(Trap state) diyeceğiz.
Burada bir geçiş tablosu yapıcak olursak
0
1
— q1
q4
q2
q2
q3
q3
q3
q3
q5
q4
q5
q5
q5
Makinenin şuan bulunduğu durum ve alfabe sonraki durumu benzersiz bir şekilde bulabiliriz.(Determinislik)
Deterministic Finite Automaton (DFA) Nedir?
Determenislik sonlu otomat olarak Türkçe ’ye çevirebiliriz.5 adet tuple’dan oluşur.
ˆ Q, durumlar adı verilen sonlu bir kümedir,
ˆ Σ alfabe denilen sonlu bir kümedir,
ˆ δ : Q × Σ → Q geçiş fonksiyonudur,
ˆ q0 ∈ Q başlangıç durumudur,
ˆ F ⊆ Q kabul durumlarının kümesidir.
A, M otomatının kabul ettiği tüm dizelerin kümesiyse, şunu deriz:
A, M otomatının dilidir ve L(M) = A yazın. Bu
M’nin A’yı tanıdığı anlamına gelir.
Örnek 1–2: Aşağıdaki otamat hangi dili tanıtıyor ?
00 ve 11 burada reddedilir.101 değeri ise kabul çıkışını tetikler.Otamat tek sayıda sembol içeren tüm durumları kabul ederken cift sayıda ifade barındıran tüm durumları reddeder.
Örnek 1–2
Yukarıdaki otamat 0 değeri geldiğinde bir değişiklik yaşanmazken 1 durumu geldiğinde sonuç üretmez.Bu otamatta çift sayıları kabul eder.
Örnek 1–3:
Yukarıdaki otamat ise 1 ile başlayan 0 ile biten tüm durumları kabul eder.
‘∑’ alfabeyi temsil etmektedir. Örneğin ∑={a,b,c} olan 4 durumlu BSO (Belirlenebilir Sonlu Otamata) diyagramını ve tanımadığı dili betimlemek istersek.
Şekil 1-Durum Diyagramı
Şekil 2-Otamata
Yukarıdaki otamada görüldüğü üzere dilin ifade ettiği a,b,c harflerinden başka bir şey yoktur. Burada dizgilerde ab veya ba’nın olmadığınıda söyleyebiliriz. Başka bir deyişle a ile b arasında en az bir c vardır.(acb,bca)Ayrıca q4 durumu için tuzak durum diyebiliriz.
Örnek 1–5:∑={0,1} olan ve içerdiği dizgilerin sembol sayısı mod 5’te 2 olan L dilini tanıyan bir BSO tasarlayalım.
L={ w | |w|≡ mod(5) }
|w| ile w dizgisinin boyutu kastedilmektedir yani bu problemde bizim 5 adet duruma bu durumlardan 1 tane sinide kabul durumu olarak belirlememiz gerekiyor.
Son
Otamatlar biçimsel dil ile üretilen nesneler.Biçimsel Diller ise belli kalıplara giribilen dillerdir.
