diff options
| -rw-r--r-- | mgr.tex | 16 |
1 files changed, 8 insertions, 8 deletions
@@ -507,14 +507,14 @@ constant time, conclude in what state the automaton $A$ will end up in on the $j$th position of $w$ if it had started in its initial state on the $i$th position. -First, look at vertex $i.q_0$, which is the vertex of $A$'s initial state in the -$i$th copy of $Q$ and note its color $c$. Now we want to answer the following -question: if we follow the edges of the graph until the $j$th copy of $Q$, what -color will we end in? First, look at $k := \breaktable[(i-1).q_0]$. If $k \geq -j$, then we know that in the $j$th copy of $Q$, the path we're interested in -still has color $c$. Find the unique vertex $j.q$ in this copy of $Q$ that's -colored with $c$. $q$ is the state we will end up in, so if it is an accepting -state answer YES, if not, answer NO. +First, look at vertex $(i-1).q_0$, which is the vertex of $A$'s initial state in +the $(i-1)$th copy of $Q$ and note its color $c$. Now we want to answer the +following question: if we follow the edges of the graph until the $j$th copy of +$Q$, what color will we end in? First, look at $k := \breaktable[(i-1).q_0]$. If +$k \geq j$, then we know that in the $j$th copy of $Q$, the path we're +interested in still has color $c$. Find the unique vertex $j.q$ in this copy of +$Q$ that's colored with $c$. $q$ is the state we will end up in, so if it is an +accepting state answer YES, if not, answer NO. If $k < j$, then jump to the $k$th copy of $Q$ and consider the vertex $k.q$, the unique vertex here colored $c$. From $k.q$, follow its single outgoing edge |