4
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.