diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2022-12-07 19:25:46 +0100 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2022-12-07 19:25:46 +0100 |
commit | 56633c5d2149f9706b6ebcb2949544cf1a2d9b86 (patch) | |
tree | e63dfc89569adfe609aa4c04d47704e40b13e9ca | |
parent | 7d66730d2de470c1ff46c8d7e0690a485658a509 (diff) |
Fix indexing
-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 |