Finite Automata and Their Graphs

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.