Springe direkt zu Inhalt

Nazar Sopiha:

Synchronizing DFA


Every engineer wants to obtain as much control over the system as possible. One of the instruments to increase control rate is a possibility to reset the system, i.e. to return it to a known state at any moment. Most of the systems can be described in state-transition form, i.e. as deterministic finite automata (DFA). The concept of resetting a DFA was introduced by Cerný (1964) and now is called a DFA synchronization. This thesis focuses on synchronization problems, such as: how to determine whether a given DFA is synchronizing and what is a length of a reset word. This problems are believed to be one of the hardest and oldest prob- lems in the theoretical computer science. After a short theory introduction, some of the discovered algorithms with their improvements are discussed. The last sec- tion contains tests implemented in Python3. In those tests a big number of DFA is generated and synchronization property is checked under different conditions. The practical part aims to give a sense of the behaviour of the synchronization property. With help of the performed tests it is shown that the most automata tend to be synchronizing, which is quite impressive and counterlogical.

Bachelor of Science (B.Sc.)