Formal Languages And Abstract Machines PDF

FORMEL DİLLER VE SOYUT MAKİNALAR Hafta 10  CHOMSKY HİYERARŞİSİ Karmaşıklık Özyinelemeli - Sayılabilir Diller : Turing Makinesi (Recursively – Enumerable Languages : Turing Machine) Bağlama...

FORMEL DİLLER VE SOYUT MAKİNALAR Hafta 10  CHOMSKY HİYERARŞİSİ Karmaşıklık Özyinelemeli - Sayılabilir Diller : Turing Makinesi (Recursively – Enumerable Languages : Turing Machine) Bağlama - Duyarlı Diller : Doğrusal – Sınırlandırılmış otomatalar (Context – Sensitive Languages : Linear – Bounded Automata) 0 1 2 3 Bağlam - Bağımsız Diller : Bas – Bırak otomataları (Context – Free Languages : Push – Down Automata) Düzenli Diller : Sonlu - Durum otomataları (Regular Language : Finite – State Automata) *(Dil : otomata) TURING MAKİNALARI TURING MACHINES  TURING’İN TANIMI... her birine bir sembolün yazılabileceği karelere ayrılmış sonsuz uzunlukta bir teyp ile elde edilen sınırsız bellek kapasitesi. Belli bir anda makinede, okunan sembol olarak adlandırılan tek bir sembol mevcuttur. Makine, okunan sembolü değiştirebilir ve davranışı kısmen bu sembol tarafından belirlenir, fakat teyp içindeki diğer sembollerin makinenin davranışı üzerinde hiçbir etkisi yoktur. Yalnız, makinenin temel işlemlerinden bir tanesi de teyp üzerinde ileriye ve geriye doğru hareket edebilmektir. Dolayısıyla, teypteki her bir sembol er ya da geç erişilebilecektir. (Turing 1948, p. 61)  FORMEL OLMAYAN BİR TANIM Bir Turing makinesi aşağıdakilerden oluşur:  (Sola ve / veya sağa doğru) sonsuza kadar uzatılabilen, her biri (özel bir boşluk sembolü de dahil olmak üzere) bir sembol içeren ardışık hücrelere ayrılmış bir teyp.  Her defasında gösterdiği hücreden bir sembol okuyup aynı hücreye bir sembol yazabilen veya bir önceki ya da sonraki hücreye kayabilen bir kafa.  Bir sonlu durumlar kümesi.  Bir geçiş fonksiyonu. Turing Makinesi = Sonlu Bir Kontrol Ünitesi + Bir Teyp  TURING’İN TANIMI  Makinenin sonlu bir iç durumlar kümesi vardır. Verili bir anda makine bu durumların birinde bulunur.  Makinenin bir okuyucu-yazıcı kafası vardır.  Bu kafanın önüne karelere bölünmüş bir sonsuz şerit ya da bant yerleştirilmiştir. Bu karelerin her biri ya boştur ya da sonlu bir simgeler kümesine ait bir simge içerir.  TURING’İN TANIMI  Makine o anda içinde bulunduğu iç duruma göre, okur-yazar kafanın önündeki karede yer alan simgenin fonksiyonu olarak (kullanılan programdaki kural listesine bakarak), 1. Bu karedeki simgeyi siler ya da bu kareye yeni bir simge yazar. 2. Şeridi bir kare sağa ya da sola yürütür. 3. Yeni bir iç duruma geçer.  TURING’İN TANIMI  Makinenin iç durumundan biri pasif durumdur. Makine bu iç duruma geçtiğinde hesaplamasını bitirmiş demektir. Turing Makinesi, işlemleri ardışık ve ayrık adımlar biçiminde gerçekleştirir. TM, hem bilgi girişi/çıkışı makineleri, hem de evet/hayır karar verme makineleridir.  TURİNG’İN TANIMI  Üzerinde belirli bir simgeler dizisi yazılı olan şerit, belirli bir karesi kafanın önüne gelecek biçimde yerleştirilir.  Makine belirli bir başlangıç durumunda olmak üzere süreci başlatır.  Bir dizi ardışık adımdan sonra pasif duruma gelip durduğunda, şerit üzerinde yazılı bulunan simgeler dizisi, hesaplamanın sonucunu oluşturur.  FORMEL BİR TURING MAKİNESİ TANIMI  Bir Turing makinesi şu yedi bileşenden oluşur: Q : Boş olmayan bir sonlu durum kümesi Γ : Boş olmayan bir simge kümesi / alfabe b ϵ Γ : boşluk sembolü ∑ ⊆ Γ \ {b} : Giriş simgelerini içeren küme Q1 : Başlangıç durumu F ⊆ Q : Bitiş durumlarını içeren küme Δ : Q \ F x Γ  Q x Γ x {L, R}, geçiş fonksiyonu (L ve R, sırasıyla bir adım sola ve bir adım sağa kayma simgeleridir). anbn | n ≥ 1 anbncn | n ≥ 1 EŞLENİK ALMA TOPLAMA İŞLEMİ (BİRLİ SİSTEM)