This question already has an answer here:

Sipser theorem 4.4*

$E_{DFA} = \{ \langle A \rangle \mid \text{A is a DFA and } L(A)=\emptyset\}$ is decidable.

I could not quite understand the solution, I'll quote it:

On input $\langle A \rangle$ where $A$ is a DFA:

  1. Mark the start state of A

  2. Repeat until no new states get marked:

  3. Mark any state that has a transition coming into it from any state that is already marked.

  4. If no accept state is marked, accept; otherwise, reject.

My question is, what does it mean to even 'mark' something in the encoding? how do we do this? The encoding is merely a word from $\{A,c\}$, how would you 'mark' states?


marked as duplicate by Hendrik Jan, frafl, Luke Mathieson, Juho, vonbrand Jan 23 '14 at 18:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


It's just a colloquialism. It means, you keep a set of states that have been marked. Initially the set is empty. When you mark a state, you add it to that set.


Assume your inputs are encoded in some alphabet $\Sigma$. You can then extend the tape alphabet to $\Sigma \cup \hat\Sigma$ (and probably some control symbols) where $\hat\Sigma = \{ \hat a \mid a \in \Sigma\}$.

Now, when you want to mark a part of the input, you just exchange the symbol(s) by its (their) marked version(s).

  • $\begingroup$ Here we're not talking about the input at all, only the states... $\endgroup$ – TheNotMe Jan 8 '14 at 11:19
  • 1
    $\begingroup$ @TheNotMe In the solution you quote, an encoding $\langle A \rangle$ of DFA $A$ is the input to the algorithm. In other words, $\langle A \rangle$ is a string, certain parts of which may correspond to the states of $A$. $\endgroup$ – Raphael Jan 8 '14 at 16:45

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