I'm looking at the book 'Mathematical Structures in Languages', and I'm confused by the way they produce a DFA from the following NFA:
They say that there must be a $d$-arrow $X\to Y$ iff $Y$ is the set of all states reachable from some state in $X$ by a $d$-arrow. Then, they say that the corresponding DFA in this case is the following:
I have two questions:
Why is there no $b$-arrow from $\{r,s\}$ to $\{r\}$? It is definitely the case that $\{r\}$ is the set of all states reachable by $b$-arrows from some state in $\{r,s\}$ (namely, from $s$).
Why is there $c$-arrow from $\{r,s\}$ to $\{r,s\}$? If we start with $r$, we won't be able to reach both $r$ and $s$ with a $c$-arrow, and similarly if we start with $s$, we won't be able to reach both $r$ and $s$ with a $c$-arrow either.
Are these two points mistakes in the book, or is my reasoning wrong?
Great questions!
Both (1) and (2) amount to the same confusion, which is how precisely to interpret "the set of all states reachable from some state in $X$ by a $d$-arrow".
The idea is that, starting at a set $X$ and reading a character $d$, we want to simultaneously follow all $d$-arrows from every state in $X$. Precisely, let's write $d \cdot q = \{ q' \mid q \overset{d}{\to} q' \}$ for the set of states we can get from $q$ by following a $d$ arrow in our NFA. Then in our powerset DFA, we add a single $d$-arrow from $X$:
$$ X \overset{d}{\longrightarrow} \bigcup_{q \in X} d \cdot q $$
Remember that, at the end of the day, we expect to get a DFA. So from any state $X$, there should be exactly one outgoing arrow for every character.
In the case of your question (1), let's look at the $b$ arrow from $\{r,s\}$. We know
So altogether we have an arrow $\{r,s\} \overset{b}{\longrightarrow} \{r, s\} \cup \{ r \}$. That is, a $b$ arrow from $\{r,s\}$ to itself. Since this is a DFA, there can be only one $b$ arrow from $\{r,s\}$, so this is the only arrow we add. In particular, there's no arrow to $\{r\}$.
Interestingly, there is a typo in your book related to your question (2). Let's look at the $c$ arrow from $\{r,s\}$. Here we have
So we have an arrow $\{r,s\} \overset{c}{\longrightarrow} \emptyset \cup \{s \}$. So there should be a single $c$ arrow from $\{r,s\}$ to $\{s\}$, but your book incorrectly adds an arrow from $\{r,s\}$ to itself.
Note that it correctly computes the $c$-arrows $\{ r \} \overset{c}{\to} \emptyset$ and $\{ s \} \overset{c}{\to} \{ s \}$.
I hope this helps ^_^