This is not how memory access works. For each character read, you need (1) to read the character, (2) to access the transition table at the appropriate state and character. In your case it seems that we're not counting (1), and so (2) is the single memory access. The speed of this access depends on how big the transition table is. If it is small enough to fit in cache (which is usually the case), then after several transitions, the entire transition table would be in cache and so would be accessed quickly. If it is too big, you will have cache misses and everything would be slower. But in both cases only the particular cell is accessed! However, data is stored in caches in chunks knows as cache lines, which could explain your confusion (cache lines are not big enough to hold the entire transition table). Note also that there are several levels of cache.