This dissertation is about defective finite automata. Several possible defects are introduced. In connection with defective automata, their usability is of interest. The original and the defective automaton can be compared to each other by different measures. When determinizing and minimizing the defective device, its size can be measured by the well known state complexity. It can be expressed depending on the number of states of the original automaton. The defective device can also be modified to accept only subsets of the accepted and rejected languages that are themselves accepted by finite automata. A new measure is introduced to compare the language of the original automaton to the one accepted by the defective one: the parameterized prefix distance. This measure is an extension of the prefix distance between words. It is shown that there only exist pairs of languages having a constant, degree k polynomial, and exponential distance. Moreover, for every constant and every polynomial, languages over a binary alphabet are constructed that have exactly that distance. From the density and census functions of regular languages the orders of possible distances between languages are derived and are shown to be decidable. The same is shown for the parameterized suffix distance. As a conclusion, a comparison between the investigated measures is given.
Verknüpfung zu Publikationen oder weiteren Datensätzen
