• Document: BM312 Ders Notları
  • Size: 858.33 KB
  • Uploaded: 2018-11-27 18:10:42
  • Status: Successfully converted


Some snippets from your converted document:

BM312 Ders Notları - 3 2014 DETERMİNİSTİK SONLU OTOMATLAR (DETERMINISTIC FINITE AUTOMATA) Bir Sonlu Otomat (FA) sabit ve sonlu kapasitede bir merkezi işlem ünitesine sahiptir. Giriş bilgisini “input tape” üzerinden “string” olarak alır. Herhangi bir çıkış üretmeden sadece giriş bilgisinin kabul edilip edilmediğini gösterir. Dil Tanıyıcı Cihaz (Language Recognition Device) olarak işlem yapar. Compiler’da “begin”, “+”, “for” gibi program birimlerinin belirlendiği sözcüksel analiz (lexical analysis) aşamasında ve protokol tanımlamalarında kullanılır. Şerit (input tape) a b a b a ……. a b a b a …….. okuma kafası Sonlu q0 q0 Kontrol q3 q1 q3 q1 Birimi q2 q2 Başlangıç Görünümü 3 Hareket Sonraki Görünüm Giriş bilgisi şerit üzerindeki “string”dir. Makinenin ana kısmı karakutudur (blackbox) ve sonlu sayıda farklı duruma sahiptir. Bu karakutu Sonlu Kontrol Birimi (Finite Control Unit) olarak adlandırılır ve hareketli okuma kafası (reading head) ile şerit üzerinde herhangi bir pozisyonda bulunan sembolü algılar.  Başlangıçta okuma kafası en soldaki kare üzerinde bulunur ve Sonlu Kontrol Birimi başlangıç durumundadır (initial state).  Otomat her seferinde şeritten bir sembol okur ve gerekli ise yeni bir duruma geçer.  Yeni duruma geçme sadece ve sadece mevcut durum ile okunan sembole bağlıdır! Bu sebeple “deterministik sonlu otomat” şeklinde isimlendirilir. 1 Yrd.Doç.Dr.Hacer KARACAN BM312 Ders Notları - 3 2014  Her sembol okunuşundan sonra okuma kafası bir sağdaki sembole geçer ve şerit üzerindeki “string” tamamlanana kadar bu şekilde okumaya devam eder.  Eğer “string” tamamlandığında otomat sonuç durumlarından (finite state(s)) birinde ise bu “string” kabul edilir.  Bir otomat tarafından kabul edilen dil, kabul edilen tüm “string”lerin kümesidir. Bir DFA quintuple (beşli) olarak tanımlanır. M = (K, ∑,δ, s, F) K sonlu sayıda durumlar kümesi ∑ alfabe δ geçiş fonksiyonu (transition function) K x ∑ ‘dan K’ ya s  K başlangıç durumu (sadece bir tane) F  K final state(s) kümesi  M otomatının sonraki duruma geçişi transition function ile belirlenir.  Eğer M otomatı q  K durumunda iken input tape’ten a  ∑ okumuşsa, δ(q, a)  K unique (tek) durumuna geçer. Örnek: M bir DFA ve M = (K, ∑,δ, s, F)şeklinde tanımlanmıştır. K = {q0, q1}, q σ δ(q, σ ) ∑ = {a, b}, q0 a q0 s = q0 q0 b q1 F = {q0} q1 a q1 q1 b q0 2 Yrd.Doç.Dr.Hacer KARACAN BM312 Ders Notları - 3 2014 L(M) içerisinde çift sayıda “b” bulunduran tüm stringlerin kümesidir. Konfigürasyon Otomatın herhangi bir andaki durumu ile şeritte sağ kısımdaki string’i (okunmamış) ifade eder. K x ∑* ’ın bir elemanıdır. Örneğin aşağıdaki otomat için konfigürasyon (q1, baba) ‘dır. a b a b a b a q0 q3 q1 q2 “├ M” gösterimi ardarda iki konfigürasyon arasında binary relation’ı ifade eder.  (q, w) ve (q’, w’) ardarda iki konfigürasyon ise (q, w) ├ M (q’, w’) şeklinde belirtilir. Burada w = aw’, a  ∑ ve δ(q, a) = q’ olmak zorundadır.  ├ M fonksiyonu K x ∑+ ‘dan K x ∑* ‘ya bir fonksiyondur.  (q, e) konfigürasyonu giriş string’inin sonunu gösterir ve otomat işlemini bitirir.  ├ M fonksiyonunun reflexive, transitive closure’u ├ * M şeklinde tanımlanır.  Bir string w  ∑* sadece ve sadece (s, w) ├ * M (q, e) ve q  F ise kabul edilir.  Sonuç olarak bir M otomatı tarafından tanınan dil L(M) olarak gösterilir ve tüm kabul edilen string’lerin kümesidir. 3 Yrd.Doç.Dr.Hacer KARACAN

Recently converted files (publicly available):