1
$\begingroup$

I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's Intro to TCS (3rd edition): enter image description here

And here is the execution graph:

enter image description here

Why after seeing a $1$ does state $q_1$ stem into three branches? And why after seeing a $1$ does $q_2$ not branch off into $q_3$ (isn't this the meaning of the empty symbol $\epsilon$, it acts as a "free pass" in case of no symbol)?

Here is Sipser's explanation, which I do not follow: enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Please edit into the body of your question: What's the first step you don't follow, and why? (The preferred way to quote text content in a question is to properly attribute it (well done), include it as text (→searcheable) and style using a block quote (see post editor help).) $\endgroup$
    – greybeard
    Mar 27, 2023 at 8:00

2 Answers 2

0
$\begingroup$

The left column shows you what symbol (0 or 1) is being consumed from the input. $\epsilon$ is not a consumed symbol, so whenever $q_2$ is visited, it could just as well be a $q_2$ or $q_3$ because of that $\epsilon$-transition.

So upon the first $0$ symbol, the machine remains in $q_1$. Then after reading the first $1$ symbol, it could have stayed in $q_1$, moved on the 1-branch to $q_2$, or moved on the 1-branch and the $\epsilon$-transition to $q_3$. This is why there are 3 branches there.

The reason you don't see $q_2$ branch to $q_2$ and $q_3$ on the second last row of that tree (on the consumption of the third 1 symbol) is because if the $\epsilon$ was read/processed immediately before the 1, then we wouldn't actually be in that $q_2$ state on that level, but in the $q_3$ state instead.

$\endgroup$
0
$\begingroup$

Oh okay, I think I see the point. Whenever an $\epsilon$ transition is encountered, it puts the resulting state on the same level as the state it came from, in order to have each row of the tree be in the same execution stage (as in they have read the same number of symbols).

$\endgroup$

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.