Abstract:
The issue concerning the number of possible labelings of directed graph's edges such that the resulting automation diagramm corresponds to a graph of a definite automaton is studied in the paper. It is proved that such a labeling is unique for a strongly-connected graph in an alphabet of two elements. In the case of an alphabet with a larger number of elements, the exponential dependence of the maximal number of labelings on the number of vertices is proved.
Key words:definite automata, automation diagramm, transition graph, labelings of automation graph, structure of automation graph.
Fulltext:
PDF file (439 kB)