Geri Dön

Succinctness analysis of finite automaton models

Sonlu özdevinir modellerinde özlülük analizi

  1. Tez No: 474347
  2. Yazar: EMRE ERDOĞAN
  3. Danışmanlar: PROF. DR. AHMET CELAL CEM SAY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Kur'an-ı Kerim'de mukayese üslubu

    Comparison style in Koran

    HATİCETÜL KÜBRA DEMİRÇİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

    DinMarmara Üniversitesi

    Temel İslam Bilimleri Ana Bilim Dalı

    PROF. DR. MUHSİN DEMİRCİ

  2. 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

    Türkçe

    2024

    DilbilimMarmara Üniversitesi

    Temel İslam Bilimleri Ana Bilim Dalı

    PROF. DR. HALİL İBRAHİM KAÇAR

  3. 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

    İngilizce

    2001

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF.DR. EROL ARKUN