# Does “not regular” imply “acceptor needs memory”?

Regular Languages, by definition, can be accepted by finite automata, which do not have memory. But if I know that a language is not regular, does that imply that any mechanism that recognizes the language must have memory?

• Do you have any formal definitions of mechanism and memory in mind? – Yuval Filmus Jan 29 '17 at 22:08
• "finite automata, which do not have memory" -- they have finite memory. – Raphael Jan 29 '17 at 22:35
• To expand on Yuval's comment, there are plenty of non-regular languages that can be decided using constant space (insuitable models). For instance, consider palindromes and two-head automata (or TMs). – Raphael Jan 29 '17 at 22:38

Every language $L \subseteq X^{\ast}$ for $X$ a finite alphabet could be accepted by the following (in general infinite) "automaton" (in the usual notation as "alphabet, states, start state, transition relation and final states") $$\mathcal A = (X, Q, L, \delta, F)$$ with $Q := \{ L/w : w \in X^{\ast} \}$, $\delta(L/w, u) := L/(wu)$ and $F := \{ L/w : \varepsilon \in L/w \}$, where $$L/w := \{ u \in X^{\ast} \mid wu \in L \}$$ is the quotient of the language (i.e. we take away prefixes from words in $L$). The set of quotients could be regarded as the states, or the memory. Which is finite if $L$ is regular (and more this construction gives a minimal finite automaton), and is infinite if $L$ is not regular (for example consider $L = \{ a^n b^n \mid n \ge 1 \}$ over $X = \{a,b\}$).