# Do multi-acceptance/multi-language automata exist in literature?

A multi-acceptance deterministic finite state automaton is a tuple $$(Q,\Sigma,\delta,q_0,T,f)$$ where

• $$Q$$, $$\Sigma$$, $$\delta: Q \times \Sigma \to Q$$, and $$q_0 \in Q$$ are defined in the standard way of DFAs;
• $$T$$ is a finite set of labels;
• $$f: Q \to 2^L$$ is a function that associates a set of labels to each state.

$$\delta^{\\*}: Q \times \Sigma^{\\*} \to Q$$ is defined in the standard way.

Such automaton recognizes $$|T|$$ languages, one for each label in $$T$$. More specifically, given a label $$t \in T$$ $$L(t) = \{x \mid f(\delta^{\\*}(q_0, x)) \ni t \}$$ or if you prefer $$L(t) = \{x \mid t \in f(\delta^{\\*}(q_0, x)) \}$$

Does this concept exists in literature? Googling "multi-acceptance DFA" and similar queries did not yield anything useful.

The reason I want to use this kind of automata is the following.

I have several classes of regular languages , e.g. $$L_1, L_2: T \to 2^{\Sigma^{\\*}}$$, which I already need to represent as DFAs, and I need to compute their union $$L: T \to 2^{\Sigma^{\\*}}$$ defined as $$L(t) = \{L_1(t) \cup L_2(t)\}$$. I think operations such as the union can be more efficient if I have a single automaton for each class of languages, instead of an automaton for each $$L(t)$$. Moreover, given the context in which I'm working, one can expect that many languages $$L(t)$$ and $$L(t')$$ are the same or have common aspects.

Do you suggest other approaches?

• – D.W.
Commented Apr 30 at 9:18
• @D.W. Thanks, I had never heard of Moore machines. Coincidentally, I this classes of languages are used as an alternative (partial) representation of epistemic states, which are usually represented as Kripke structures. Commented Apr 30 at 9:27

There have been studies on something called colored finite automata, which seem very close to your definition. Other colored models, e.g. regular expressions, also exist.

I haven't work on this personally so I'm not informed on the literature, but they are studied e.g. in https://doi.org/10.1587/transinf.2021FCP0012