Residual Finite State Automata Denis (2001)
In this paper, we study a subclass of non deterministic finite automata that we call Residual Finite State Automata (RFSA). By definition, a RFSA is a NFA all the states of which define residual languages of the language it recognizes. More precisely, a NFA A = ⟨Σ,Q,Q0,F,δ⟩ is a RFSA if for every state q in Q there exists a word u such that uv is recognized by A if and only if reading v, a final state can be reached from q. Clearly, all DFA are RFSA but the converse is false.
Denis2001ResidualFiniteStateAutomata.pdf
—
PDF document,
182 kB (186844 bytes)