Proof of decidability of determining whether a DFA accepts a string

Question

I want to ask the acceptance problem: Whether a particular deterministic finite automaton accepts a given string can be expressed as a language, $A_{DFA}$. Show $A_{DFA}$ is decidable. The proof in the textbook (Siper page 195) uses two steps:

$M$ = “On input $\langle B,w\rangle$, where $B$ is a DFA and $w$ is a string:

1. Simulate $B$ on input $w$.

2. If the simulation ends in an accept state, accept. If it ends in a nonaccepting state, reject .”

What exactly is the meaning of "simulating $B$" in the first step? In my understanding, if $M$ wants simulates multiple DFA $B$, the parameters of $M$ (transition function or acceptance state) need to be changed according to the different input DFA $B$ and input string $w$, since different DFAs may have different structure. In other words, can a TM simulate infinite DFAs? And how it can be done? I know this question may be trivial, but it really bugs me. Any clarification will be appreciated.

Answer 1

I've often found that, with problems like these, it's easiest to reason by analogy to software, since anything you can do with a computer you can do with a TM and vice versa (with a giant asterisk). The problem $A_{DFA}$ essentially is the following: given a DFA $D$ and a string $w$, determine whether $D$ accepts $w$. In software, you could imagine that you'd want to write a method

bool accepts(DFA D, string w)

that takes as input a DFA $D$ and a string $w$, then returns the answer. Notice that we're given the DFA as a parameter, since if we don't have it, then there's no way that we can answer the question. It would be like someone saying "I'm hiding a DFA behind my back - can you guess whether it accepts a given string?"

The pseudocode for this function might look something like this:

bool accepts(DFA D, string w) {
    currState = D.startState;
    for (char ch: w) {
        currState = D.transitionTable[currState][ch];
    }
    return D.isAcceptingState(currState);
}

Since this is something that we can do with a computer, it's certainly something that we can do with a TM.

Given this code, it's probably clearer what the TM you described above would do. It doesn't take in infinitely many DFAs or strings - it just takes in a single DFA and a single string at a time. There are infinitely many possible choices for what that DFA could look like or what that string could be, but at any one point in time the TM works on just a single string and a single DFA. The fact that the TM (or this code) correctly works on every possible DFA and every possible string is why $A_{DFA}$ is decidable: there's a TM that, given an arbitrary string, decides whether it's in the language.