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

1 Answer

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\}$).

So in short in this (somehow canonical) model even a regular language has some kind of memory (a state which signalizes some property of the string being processed), but the crucial property is that we can get along with finitely many (memory) states, whereas in the non-regular case in this model we always need an "unbounded" memory/states.