Succinctness analysis of finite automaton models
Sonlu özdevinir modellerinde özlülük analizi
- Tez No: 474347
- Danışmanlar: PROF. DR. AHMET CELAL CEM SAY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 126
Özet
Sonlu özdevinir ya da sonlu durum makinesi, bilgisayımda kullanılan matematiksel bir modeldir ve özdevinir teorisinde en çok çalışılan modellerden biridir. Yıllar boyunca deterministik, nondeterministik, olasılıksal ve kuantum özdevinir gibi sonlu durum makinelerinin birçok farklı çeşidi önerilmiştir. Ayrıca, bu özdevinir modellerinin birbirleri arasındaki ilişkileri ve biçimsel dillerle olan bağları üzerine ayrıntılı çalışmalar yapılmıştır. Bu tezde, özdevinir modellerinde özlülük özelliği üzerine çözümlemeler yapılmıştır. Konu kapsamı, üç ana başlık altında ayrıntılandırılmıştır. İlk olarak, çeşitli sonlu makine modellerinin deterministik özdevinirler tarafından simüle edilmesi konusunda yapılan çalışmalar yer almıştır. İkinci olarak, üç düzenli dil ailesi tanımlanmış ve bu dil ailelerinin farklı özdevinir modelleri tarafından en az kaç durum ile tanınacağı gösterilmiştir. Üçüncü olarak, tek harfli alfabeler kullanılarak yaratılabilecek düzenli dilleri ve bu dilleri tanıyan sonlu makineleri birlikte tanımlayan bir biçim geliştirilmiştir. Adı,“Tekli Sonlu Periyodik Biçim”olan bu form kullanılarak düzenli dillerin kapalılık özellikleri üzerine detaylıca çalışılmıştır.
Özet (Çeviri)
Finite state automaton, or finite automaton, is a mathematical model of computation and has been one of the most studied models in automata theory. Throughout the years, many different types of finite state automata are proposed, such as deterministic, nondeterministic, probabilistic, and quantum automata. Furthermore, the important questions that how they are related to each other, and how they are related to formal languages, have been a subject of intensive research. In this thesis, we study the succinctness properties of various finite automata. First, we thoroughly study the topic of simulating various finite automata by deterministic finite automata. Second, we work with three different families of regular languages and we provide the various minimal automata (i.e. minimal in the sense of the number of states used) deciding them. Third, we provide a descriptive form called“Unary Finite Periodic Form”, or shortly UFPF, to efficiently describe regular languages over unary alphabets and we introduce algorithms to show the efficient realization of closure properties of UFPF.
Benzer Tezler
- Kur'an-ı Kerim'de mukayese üslubu
Comparison style in Koran
HATİCETÜL KÜBRA DEMİRÇİN
Yüksek Lisans
Türkçe
2012
DinMarmara ÜniversitesiTemel İslam Bilimleri Ana Bilim Dalı
PROF. DR. MUHSİN DEMİRCİ
- Kelimede gerçekleşen harf hazifleri ve Kur'an-ı Kerim'deki edebî boyutu
Ellipsis of letter at the word and it's rhetoric dimensions in the Qur'an
ELANUR BAYSAN
Yüksek Lisans
Türkçe
2024
DilbilimMarmara ÜniversitesiTemel İslam Bilimleri Ana Bilim Dalı
PROF. DR. HALİL İBRAHİM KAÇAR
- A constraint-based incremental approach for update of large itemsets
Yoğun nesne kümelerinin güncellenmesi için sıralamaya dayalı artımlı bir yaklaşım
ENGİN DEMİR
Yüksek Lisans
İngilizce
2001
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF.DR. EROL ARKUN