2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for your detailed explanation, I guess the reason I got confused is that I am worried too much about the details of Turing Machine, thus I was not able to connect TM with a Program to get a more clear picture. Thank you. $\endgroup$
    – Zhiwei Pan
    Mar 25, 2017 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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