Skip to content

MFA

A memory automaton is a classical NFA that is equipped with a finite number of k memory cells, each capable of storing a word. Each memory is either closed, which means that it is not affected in a transition, or open, which means that the currently scanned input symbol is appended to its content. In a transition it is possible to consult a closed memory, which means that its content, if it is a prefix of the remaining input, is consumed in one step from the input and, furthermore, also stored in all the open memories. A closed memory can be opened again, but then it completely loses its previous content; thus, memories are not able to store subsequences, but only factors of the input.

Characterising REGEX languages by regular languages equipped with factor-referencing

Can recognize RE with backreferences (or something pretty similar)