We propose a parametrisation of SSM transition matrices that enables SSMs to track states of arbitrary finite-state automata while keeping the cost of the parallel scan comparable to that of diagonal SSMs.