Measuring defects in finite automata

Abstract

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.

Die vorliegende Dissertation behandelt Defekte in endlichen Automaten. Verschiedene Defekte werden näher betrachtet und bezüglich der Nutzbarkeit des durch sie entstehenden defekten endlichen Automaten untersucht. Hierfür werden unterschiedliche Maße verwendet. Mit Hilfe der Zustandskomplexität werden der originale Automat und Abwandlungen des defekten Automaten miteinander in ihrer Größe verglichen. Das neu eingeführte Maß der parametrisierten Präfix-Distanz vergleicht die Distanz zwischen den akzeptierten Sprachen des originalen und defekten Automaten. Für dieses Maß wird gezeigt, dass jedes mögliche Paar regulärer Sprachen keine beliebige Distanz besitzen können. Es sind nur konstante, polynomielle oder exponentielle Distanzen möglich. Für jede beliebige Distanz innerhalb dieser Distanzklassen ist es möglich, zwei Sprachen zu konstruieren, die genau die vorgegebene Distanz besitzen. Für gegebene Sprachen ist deren Distanz entscheidbar. Abschließend werden die untersuchten Maße in Bezug auf die Nutzbarkeit der defekten Automaten verglichen.