# DFA memory bandwidth

When we talk about DFA, we say that each new character from the input requires one memory access. What does that mean?

This is what I think about this. Please tell me is this right? For example, I have a transition table stored for a certain regular expression in memory (RAM). Now, for each input character the CPU will fetch the whole transition table to find out the next state. In this way, we have just one memory access?

• DFA are their own model in which there is no such thing as "memory". So I take it you are talking about an implementation of an algorithm that is derived from a DFA. In which machine model do you want to analyse memory accesses then?
– Raphael
Nov 2, 2015 at 17:25
• @Raphael. Minor nit, but I take issue with your assertion that a DFA has no memory. It "remembers" its current state, and, as we know, that can be used to "remember" the sequence of the most recent $k$ inputs, for a fixed $k$. Nov 3, 2015 at 1:36