| Abstrakt: | The concept of state complexity is crucial for understanding and categorizing computational problems, as well as for measuring and comparing the efficiency of various computational models. A significant area of study in this field is the comparison of the state complexity of two-way deterministic and nondeterministic finite automata, as well as one-way deterministic and nondeterministic finite automata. For one-way finite automata, it is known that there exists a sequence of languages where a one-way deterministic finite automaton needs exponentially more states to accept them than a one-way nondeterministic finite automaton. However, for two-way automata, this question remains open. Therefore, researchers focus on studying modifications of these two-way automata. In this thesis, we primarily focus on the state complexity of a model called drunken finite automata, which represent a modification of two-way automata that have no control over the head's movement direction. Instead, the head moves according to the drunkard's walk random process, and the direction of the last movement is the input to the automaton's transition function. Whenever the automaton reaches the end marker of the input word, it must be in the correct accepting or rejecting state. In this work, we first show that drunken finite automata accept the set of regular languages and then focus on examining the state complexity of their deterministic and nondeterministic versions in comparison with finite automata. Special attention is given to comparing the state complexity of these models for regular languages over unary alphabets. We also demonstrate that there exists a sequence of languages where a drunken deterministic automaton needs exponentially more states to accept them than a drunken nondeterministic automaton.
|
|---|