A standard state machine with no memory (other than the current state) is equivalent in expressivity to regexes (in fact regexes with back-references are more expressive); even if the state machine is non-deterministic.