m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2022-12-07 19:25:46 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2022-12-07 19:25:46 +0100
commit56633c5d2149f9706b6ebcb2949544cf1a2d9b86 (patch)
treee63dfc89569adfe609aa4c04d47704e40b13e9ca
parent7d66730d2de470c1ff46c8d7e0690a485658a509 (diff)
Fix indexing
-rw-r--r--mgr.tex16
1 files changed, 8 insertions, 8 deletions
diff --git a/mgr.tex b/mgr.tex
index 07c3c6e..787cd91 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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