2
$\begingroup$

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:

enter image description here

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:

enter image description here

I have two questions:

  1. 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$).

  2. 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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

  • $b \cdot r = \{ r, s \}$
  • $b \cdot s = \{ r \}$

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

  • $c \cdot r = \emptyset$
  • $c \cdot s = \{ s \}$

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 ^_^

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .