On Concatenative Decompositions of Regular Events

Abstract—Finding simple or "canonical representations" for regular events is one of the important problems concerning finite automata. The present paper is an attempt to find concatenative canonical decompositions for regular events. Five different decomposition types of regular events are defined, imustrated by examples, and their properties investigated. The main tool in our investigations is the notion of a decomposition set; it is a generalization of the notion of a decomposition state, introduced by the authors in a previous paper.^[7]Let A =(S, M, s0, F) be a finite automaton; a subset S̄⊂S is a decomposition set if A goes through a state of S̄ whenever it accepts a tape. In order to determine whether a given subset S̄⊂S is a decomposition set one has to check only tapes whose length is not greater than |S|-|S̄|-1, where |S| and |S̄| are the number of states in S and S̄, respectively. Thus, one can deternine all decomposition sets of A. The knowledge of the decomposition sets of A enables one to determine whether and in what form T(A), the set of tapes accepted by A, is decomposable.