0
$\begingroup$

Michael Sipser's Introduction to Theory of Computation: Book screenshot

Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a state of M.

It also says that E(R) is 'the collection of states that can be reached from members of R by going only along ε arrows, including the members of R themselves' which means that both R and E(R) are sets of states of N.

But then it says that 'q', an element of E(R) can contain, can be reached from 'R'. The problem is that 'q' is an element of E(R) which is a set of states of N while R is a state of M. How can you reach a state of N from one of M?

$\endgroup$
2
  • $\begingroup$ DFAs have no $\epsilon$-transitions. This needs to be taken into account when trying to decypher such a definition in that reachability via $\epsilon$-transitions must refer to reachability in $N$, not $M$. It is then clear that "can be reached from $R$" means "can be reached from an element of $R$". This is perhaps terse but not ambiguous. $\endgroup$
    – Kai
    Mar 4, 2023 at 22:26
  • $\begingroup$ Thank you for the explanation $\endgroup$
    – Sbeve
    Mar 7, 2023 at 11:02

1 Answer 1

1
$\begingroup$

To clarify, I think they meant that $$E(R)=\{q|\exists s\in R, q\text{ can be reached from $s$ by $0$ or more $\epsilon$ transitions}\}$$

$\endgroup$
4
  • $\begingroup$ So to be clear, the definition provided is wrong, right? $\endgroup$
    – Sbeve
    Mar 4, 2023 at 12:37
  • $\begingroup$ I would say its more ambiguous than wrong, since anyways it seems they didn't write it formally. $\endgroup$
    – nir shahar
    Mar 4, 2023 at 12:39
  • $\begingroup$ Thanks, accepting your answer $\endgroup$
    – Sbeve
    Mar 7, 2023 at 11:02
  • $\begingroup$ Glad that I could help :) $\endgroup$
    – nir shahar
    Mar 7, 2023 at 14:43

Your Answer

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

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