12
$\begingroup$

I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one transition labeled with $a$. (Of course, the automaton is then necessarily a partial deterministic automaton.) Is there a name for this class of regular languages?

These languages are quite limited but not entirely trivial either, for instance you could have $(ab)^*$, $ab^*|cd^*$, or $(ab)^*a$ (which I guess cannot be written as a regular expression with only one occurrence of each letter, so my class is more general than imposing the analogous requirement on regular expressions). These automata are clearly local automata, so this is a subclass of the local languages. These automata are also aperiodic, so these languages are star-free. Of course, for any alphabet, there are only finitely many languages of this kind over the alphabet.

I thought this class was pretty natural, but looking around, I could not find anything about it. Does it have a name, or has it been studied somehow?

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ It seems that your class can be defined as the smallest class $C$ such that every regular language is the projection via a length-preserving morphism of a language from $C$. Maybe this algebraic point of view can help... $\endgroup$ – Denis Nov 1 '20 at 22:49
  • 1
    $\begingroup$ Actually, a deterministic automaton has exactly as many $a$-transitions as it has states. Do you mean something like a “partial deterministic” automaton? $\endgroup$ – Emil Jeřábek Nov 2 '20 at 9:10
  • 1
    $\begingroup$ @Denis: I agree with your comment, though I'm not sure how to use it. :) $\endgroup$ – a3nm Nov 2 '20 at 10:46
  • 1
    $\begingroup$ They are a subclass of the reversible automata but I don't know if they are "studied" or have an "official" name; see for example On Reversible Automata. Given a DFA you can expand its alphabet to assign an unique letter to each transition, the resulting language is the language of all possible traversals ("traces") of the original DFA. $\endgroup$ – Marzio De Biasi Nov 2 '20 at 12:27
  • 1
    $\begingroup$ @a3nm if an automaton works, then there is no way to further minimize it by merging states, since the outgoing transitions of two different states have completely different labels. $\endgroup$ – Denis Nov 2 '20 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.