Otomata Teorisi #09 | Sonlu durumlarla hesaplama

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

Masamızdaki inceleme lambası başlangıçta sönük. Bir darbe komutu gönderiyoruz ve ışık yanıyor. Darbe lambanın durumunu değiştiriyor. Ardından tut komutu geldiğinde ışık yanmaya devam ediyor. Yeni bir darbe ise onu yeniden söndürüyor. Üç boyutlu mekanizmanın hareketini izlerken yalnız düğmeye bakmayın; komuttan hemen önce lambanın hangi durumda bulunduğunu da takip edin. Sonucu belirleyen bilgi bu iki parçanın birlikte değerlendirilmesinde. Üç boyutlu bir lamba denetleyicisinde darbe, tut ve sıfırla komutlarını izliyoruz. Ardından 01 ile biten ikili sözcükleri ayıran özgün üç durumlu makineyi kuruyor; kabul durumuna uğramakla bütün girdinin bitmesini birbirinden ayırıyoruz. Bu derste: 1. Neyi hatırlamak gerekiyor? 2. Üç komut, altı kural 3. Yedi komutu tek tek izle 4. Sözcüğün sonu 01 mi? 5. Üç durum, altı geçiş 6. 00101 üzerinde çalışan makine 7. Kabul durumundan çıkabiliriz 8. Boş sözcük ve kısa denemeler 9. Farklı geçmişler, aynı gelecek 10. Uzun girdi, sabit kontrol belleği Bölümler: 0:00 Aynı komut, farklı sonuç 1:23 Neyi hatırlamak gerekiyor? 2:46 Üç komut, altı kural 4:01 Yedi komutu tek tek izle 5:20 Sözcüğün sonu 01 mi? 6:39 Üç durum, altı geçiş 8:08 00101 üzerinde çalışan makine 9:25 Kabul durumundan çıkabiliriz 10:49 Boş sözcük ve kısa denemeler 12:12 Farklı geçmişler, aynı gelecek 13:33 Uzun girdi, sabit kontrol belleği 14:53 Durumu oku, geçişi izle, bitişi ayır Kaynak kitap: Michael Sipser, Introduction to the Theory of Computation, Third Edition; Chapter1 introduction and §1.1 Finite automata before formal definition. Basılı 31–34 / fiziksel PDF 55–58, bölüm 1 girişi ve §1.1 formal tanım öncesi. Fiziksel 59 yalnız sonraki dersin sınır bağlamıdır; beşli formal tanım bu dersin kapsamına dahil değildir. Konu sırası kaynaktan izlenir; anlatım, lamba modeli ve 01 ile bitiş makinesi özgündür. Lamba komutunun sonucu mevcut durumla birlikte belirlenir. Üç durumlu makinede boş girdi reddedilir; 00101 kabul edilirken 001010 ve 001011 reddedilir. Ara C ziyareti sırasında girdi sürüyorsa nihai kabul kararı verilmez. Aynı durumda birleşen önekler aynı devamla aynı geleceği üretir; aynı anlık ret kararı ise aynı durum anlamına gelmez. Görünen geçmiş şeridi dışsal öğretim kaydıdır. Blender mekanizması fiziksel devre simülasyonu değildir; mantıksal geçiş sayısı duvar saati hız ölçümü değildir. Sonlu bağımsız uygulama testleri genel deterministik gerekçenin yerine geçmez. Hedef kitle: bilgisayar mühendisliği ve kuramsal bilgisayar bilimine giriş öğrencileri.