Finite Automata and Their Graphs

Abstract

Finite automata are one of the most known topics of (theoretical) computer science. Their presentations by their graphs are well known and widely used. In this thesis, these representations will be analyzed from a graph theoretical point of view. In this way, the work is also related to graph theory and combinatorics. The finite automata are used to accept formal languages and the accepted language class may be characterized by some graph theoretical properties of the used automata. We define five different types of Strongly connected automata as, Line directed, Directed cycle, Bidirected cycle, Starred, and Floral automata, and their constructions were studied from a graphical point of view. The class of languages accepted by these automata was also studied by regular expressions. While keeping the initial state constant, we vary each state of the automata to be the final state, and using the elimination method, we obtain the regular expression these automata accept. We also define the concept of Hamiltonian-like words as words accepted by automata that pass through all states of the automata. Then, we studied the Hamiltonian-like words accepted by the defined strongly connected automata while varying the final state. Properties of these Hamiltonian-like words, such as length, Kleene stars, and cycles, were investigated. Keywords: Finite Automata, Strongly Connected Automata, Hamiltonian-like Words.

Sonlu otomatlar (sonlu durum otomatları) (teorik) bilgisayar bilimlerinin en bilinen konularından biridir. Grafikler aracılığı ile temsiliyetleri iyi bilinir ve yaygın olarak kullanılır. Bu tezde, bu sunumlar bir teorik grafik bakış açısıyla analiz edilecektir. Bu şekilde çalışma, grafik teorisi ve kombinatorik araştırma konularına da bağlıdır. Otomatlar, resmi dilleri kabul etmek için kullanılır ve kabul edilen dil sınıfı, kullanılan otomatların bazı grafik teorik özellikleri ile karakterize edilebilir. Aralarında güçlü bağlantı bulunan beş farklı totomat çeşidini; Çizgi yönelimli, Yönlü çevrim, Çift yönlü çevrim, Yıldızlı ve Çiçekli otomatları tanımladık ve bunların yapıları grafiksel bir bakış açısıyla incelendi. Bu otomatlar tarafından kabul edilen dil sınıfı düzenli dillerle de incelenmiştir. İlk durumu sabit tutarak, otomatların her durumunu son durum olacak şekilde değiştirerek ve yok etme yöntemini kullanarak, bu otomatların kabul ettiği düzenli dil sınıfını elde ettik. Hamilton benzeri kelimeler kavramını da otomatların kabul ettiği ve otomatların tüm durumlarından geçen kelimeler olarak tanımlıyoruz. Daha sonra, son durumu değiştirirken yukarıda tanımlanan bağlantılı otomatlar tarafından kabul edilen Hamilton benzeri kelimeleri inceledik. Uzunluk, Kleene yıldızları ve döngüler gibi bu Hamilton benzeri kelimelerin özellikleri araştırıldı. Anahtar Kelimeler: Sonlu Otomat, Yakın Bağlantılı Otomatlar, Hamiltoniyen Benzeri Kelimeler.