Otomata Teorisi #05 | Sözcükler ve biçimsel diller

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

Ekranda altı kutuluk bir şerit açılıyor. Kutularda sırayla a, be, be, a, be ve a var. Şimdi yalnız hangi işaretleri kullandığımıza değil, bu işaretlerin hangi konumlarda bulunduğuna bakalım. Aynı iki işaretle çok farklı şeritler kurabiliriz. İki kutunun yerini değiştirmek kullandığımız işaret kümesini koruyabilir, fakat sözcüğün kendisini değiştirebilir. Bugün küme ile sıralı diziyi yeniden ayırarak biçimsel dillerin temel nesnelerini kuracağız. Aynı sembollerden farklı sözcükler kuruyoruz. Özgün abbaba şeridinde ters çevirme, bitişim, kuvvet, alt sözcük ve önek işlemlerini izliyoruz. Boş sözcüğü boş dilden ayırıyor; seçilmiş sembol sırasıyla kısa sözcükleri sıralıyor ve dil üyeleri arasında öneksizlik koşulunu denetliyoruz. Bu derste: 1. Önce kullanılabilen sembolleri belirle 2. Kutusu olmayan bir sözcük 3. Sembolleri değiştirmeden konumları tersle 4. Soldaki şeridin arkasına sağdakini ekle 5. Üs, aynı sözcüğün tekrar sayısıdır 6. Alt sözcük için komşu konumlar gerekir 7. Başlangıca bağlı bir eşleşme 8. Önce uzunluk, sonra seçilmiş sembol sırası 9. Sözcüklerden oluşan küme 10. İki farklı üyeyi birlikte kontrol et Bölümler: 0:00 Aynı semboller, farklı sözcükler 1:27 Önce kullanılabilen sembolleri belirle 2:47 Kutusu olmayan bir sözcük 4:07 Sembolleri değiştirmeden konumları tersle 5:30 Soldaki şeridin arkasına sağdakini ekle 6:54 Üs, aynı sözcüğün tekrar sayısıdır 8:19 Alt sözcük için komşu konumlar gerekir 9:44 Başlangıca bağlı bir eşleşme 11:08 Önce uzunluk, sonra seçilmiş sembol sırası 12:37 Sözcüklerden oluşan küme 14:03 İki farklı üyeyi birlikte kontrol et 15:28 Nesnenin düzeyini ve koşulunu birlikte söyle Kaynak kitap: Michael Sipser, Introduction to the Theory of Computation, Third Edition; §0.2 Strings and languages. Basılı 13–14 / fiziksel PDF 37–38, §0.2 Strings and languages, prefix-free tanımının sonuna kadar. Konu sırası kaynaktan izlenir; anlatım, çizimler ve örnekler özgündür. TypeScript atomik sembol dizileri, bağımsız Python tuple ve küme yöntemleriyle çapraz denetlenmiştir. Alfabe sonlu ve boş olmayan bir sembol kümesidir. Sözcükte sıra ve tekrar korunur. Boş sözcük, boş dil ve yalnız boş sözcüğü içeren dil farklıdır. Alt sözcük ardışık konumlara; önek başlangıca bağlıdır. Öz önek sözcüğün kendisinden farklıdır. Kısa sözcük sıralaması seçilen sembol sırasına bağlıdır. Dil üyeler arasında tekrarı yok sayar. Öneksizlik farklı üyeler arasındaki öz önek tanığını yasaklar. Sonlu örnek kontrolleri genel teorem, kararverilebilirlik, donanım hızı veya güvenlik kanıtı değildir. Hedef kitle: bilgisayar mühendisliği ve kuramsal bilgisayar bilimine giriş öğrencileri.