We present deterministic suffix-reading automata (DSA), a new automaton model over finite words. Our motivation for this model comes from specifications which can be described using rules of the form: "when a certain sequence of inputs is seen, perform this action". DSAs provide a cleaner representation, compared to deterministic finite automata (DFA), in such situations.
Transitions of a DSA are labeled with words. From a state, a DSA triggers an outgoing transition when a word ending with the transition-label is seen. Therefore, rather than moving along an input word letter by letter, a DSA can jump along blocks of letters, with each block ending in a suitable suffix. This feature allows DSAs to recognize regular languages more concisely.
In the talk, we will describe a procedure to construct a minimal DSA for a regular language, starting from its minimal DFA.
Joint work with R Keerthan, R Venkatesh and Sagar Verma.