Deterministic Finite Automata (DFAs) are of central importance in automata theory. In view of how state diagrams for DFAs are defined using directed graphs, this leads us to introduce a generalization of DFAs related to a method widely used in graph theory referred to as the discharging method. Given a DFA $(Q, \Sigma, \delta, q_{ 0}, F)$, the transition function $\delta\colon Q \times \Sigma \to Q$ determines a directed path in the corresponding state diagram based on an input string $a_{ 1} a_{ 2} \cdots a_{ n}$ consisting of characters in $\Sigma$, and our generalization can be thought of as being based on how each vertex in $D$ ''discharges'' rational values to adjacent vertices (by analogy with the discharging method) depending on the string $a_{ 1} a_{ 2} \cdots a_{ n}$ and according to a fixed set of rules. We formalize this notion and pursue an exploration of the notion of a Discharging Deterministic Finite Automaton (DDFA) introduced in this paper. Our DDFA construction gives rise to a ring structure consisting of sequences that we refer to as being quasi-$k$-regular, and this ring generalizes the ring of $k$-regular sequences introduced by Allouche and Shallit.

Categories: cs.FL math.CO

A generalization of Deterministic Finite Automata related to discharging