Meno: | Matúą
|
---|
Priezvisko: | Juran
|
---|
Názov: | Longest Shortest Words in Regular Languages
|
---|
Vedúci: | RNDr. Peter Kostolányi, PhD.
|
---|
Rok: | 2021
|
---|
Kµúčové slová: | shortest word, rotating finite automaton, alternating finite automaton
|
---|
Abstrakt: | In this thesis, we study the following problem: given an automaton with a given number of states, how long can the shortest accepted word potentially be? This problem was studied in the past in the case of nondeterministic finite automata and two-way automata. We provide an overview of relevant previous results and define the function lsw which generalizes this problem to sequences of finite sets of languages. Then, we study the problem with rotating finite automata and alternating finite automata as models of choice. We describe lower and upper bounds for accepted languages, their intersections and complements for alphabets of various sizes. Lastly, we compare the values that the function lsw attains for sequences defined by certain models.
|
---|