1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Raphael
    Nov 2, 2015 at 17:25
  • $\begingroup$ @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$. $\endgroup$ Nov 3, 2015 at 1:36

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So, when the transition table is large then we can't access the whole transition table in one memory access? Isn't it? $\endgroup$
    – Xara
    Oct 7, 2013 at 17:54
  • $\begingroup$ It's still one memory access, but it's more expensive since you're accessing the main memory rather than the cache. $\endgroup$ Oct 7, 2013 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.