# How to mark things in the input? [duplicate]

### 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, vonbrandJan 23 '14 at 18:46

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\}$.
• @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$. – Raphael Jan 8 '14 at 16:45