Otomata Teorisi #10 | Sonlu Otomatın Biçimsel Tanımı

Eğitmen: Dr. Süleyman Burak ÇELİK

Önümüzde iki küçük döner gösterge var. Her biri çift ya da tek konumunda durabiliyor. İkisi de çift konumunda başlasın. A simgesi geldiğinde yalnız ilk göstergeyi ters çeviriyoruz. Ardından be simgesi geldiğinde yalnız ikinciyi çeviriyoruz. Hareketi izlerken iki ayrı bilginin aynı anda taşındığına dikkat edin. Birinci gösterge okunan a sayısının, ikincisi okunan be sayısının tek mi çift mi olduğunu anlatıyor. İki döner göstergede a ve b sayılarının tek ve çift bilgisini izliyoruz. Özgün dört durumlu makine üzerinden beşli tanımı, geçiş fonksiyonunu, doğru koşuyu ve girdi bitimindeki kabulü birlikte kuruyoruz. Bu derste: 1. Beş parçanın ayrı görevi 2. Dört durumun anlamı 3. Bir durum ile bir simge 4. Sekiz hücrenin her biri dolu 5. Yedi simgenin koşusu 6. Bir koşuyu biçimsel olarak oku 7. Sondaki halka tek başına yetmez 8. Kabul ziyareti ile bitiş 9. Boş sözcük ile boş dil 10. Bir makine, tanıdığı bir dil Bölümler: 0:00 İki gösterge, dört olasılık 1:22 Beş parçanın ayrı görevi 2:42 Dört durumun anlamı 4:00 Bir durum ile bir simge 5:20 Sekiz hücrenin her biri dolu 6:37 Yedi simgenin koşusu 7:57 Bir koşuyu biçimsel olarak oku 9:19 Sondaki halka tek başına yetmez 10:43 Kabul ziyareti ile bitiş 12:02 Boş sözcük ile boş dil 13:27 Bir makine, tanıdığı bir dil 14:47 Neden doğru, neden düzenli? Kaynak kitap: Michael Sipser, Introduction to the Theory of Computation, Third Edition; §1.1 formal definition and computation. Basılı35–41 / fizikselPDF59–65, Definition1.5 biçimsel tanımdan Example1.17 sonuna; Designing finite automata başlığı ve sonrası kapsam dışıdır. Konu sırası kaynaktan izlenir; anlatım, iki göstergeli model ve parite makinesi özgündür. Başlangıç ÇÇ, kabul ÇT: ilk konum a, ikinci konum b sayısını özetler. aabbaba yedi geçişte kabul edilir; aabbabaa reddedilir. Ara kabul ziyareti, kalan girdi varken nihai karar değildir. Geçerli ret koşusu ile hatalı aday dizi ayrılır. Boş sözcük, boş dil ve yalnız boş sözcüğü içeren küme farklıdır. Kabul kümesini değiştirmek yeni makine tanımlar; F boş olabilir. Durum anlamının başlangıç ve her adımda korunması genel gerekçeyi verir; sınırlı uygulama testleri bunun yerine geçmez. Düzenlilik, dili tanıyan bir sonlu otomatın varlığıyla açıklanır; minimallik veya duvar saati hız iddiası yoktur. Blender mekanizması soyut durum güncellemesini gösterir; fiziksel devre simülasyonu değildir. Hedef kitle: bilgisayar mühendisliği ve kuramsal bilgisayar bilimine giriş öğrencileri.

Bu videoyu izlemek için Premium üyelik gerekir.