diff options
| -rw-r--r-- | mgr.tex | 34 |
1 files changed, 18 insertions, 16 deletions
@@ -1098,12 +1098,13 @@ automaton, allowing us to use our result from Chapter \ref{branchinfix}. To show this formally, consider the alphabet $\Sigma' := Q \times \Sigma \times Q \times \{ \leftsymbol, \rightsymbol \}$. A word over this alphabet can be used to represent a subtree with a hole. A subtree with hole as described above would be -represented by word $a_0 a_1 \ldots a_p$ with each $a_i$ being a quadruple -from $\Sigma'$, $\langle p_i, b_i, q_i, d_i \rangle$ (with $p_i, q_i \in Q$, -$b_i \in \Sigma$, $d_i$ either $\leftsymbol$ or $\rightsymbol$) where: +represented by word $\alpha_0 \alpha_1 \ldots \alpha_p$ with each $\alpha_i$ +being a quadruple from $\Sigma'$, $\langle p_i, a_i, q_i, d_i \rangle$ (with +$p_i, q_i \in Q$, $a_i \in \Sigma$, $d_i$ either $\leftsymbol$ or +$\rightsymbol$) where: \begin{itemize} - \item $b_i$ is the original label of $u_i$. + \item $a_i$ is the original label of $u_i$. \item $p_i$ and $q_i$ are the states of $u_i$'s children in the precomputed run of $A$ over $T$. \item $d_i$ encodes the information of whether $u_i$ is the left or right @@ -1117,9 +1118,10 @@ when considering just one subtree with hole and can be ignored when doing computation on that particular subtree with hole. But we will keep information about both children so that we can handle questions about any subtree with hole. -Now consider the language $L_{q,q'} \subseteq \Sigma'^*$ of words $a_0 \ldots -a_p$ such that the subtree with hole encoded by such a word, if the hole's state -were set to $q$, would lead to $A$ arriving at state $q'$ after running up it. +Now consider the language $L_{q,q'} \subseteq \Sigma'^*$ of words $\alpha_0 +\ldots \alpha_p$ such that the subtree with hole encoded by such a word, if the +hole's state were set to $q$, would lead to $A$ arriving at state $q'$ after +running up it. \begin{lemma} $L_{q,q'}$ is a regular language. @@ -1132,15 +1134,15 @@ by the previously read letter, what state we arrived in at it and whether it was the current vertex's left or right child. The automaton works as follows: \begin{enumerate} - \item In the initial state $\mathsf{initial}$, read $a_0 = \langle p_0, b_0, - q_0, d_0 \rangle$, set the state to $\langle q, d_0 \rangle$. - \item Now when reading letter $\langle p_i, b_i, q_i, d_i \rangle$ in state - $\langle r, d \rangle$, if $d$ if $\leftsymbol$, use $A$'s transition - function $\delta$ to compute the new tree state as $\delta(r, b_i, q_i)$ - (the previously computed tree state is of our left child's, and our - right child's comes from the current letter). If $d$ is $\rightsymbol$, - the new tree state will instead be $\delta(p_i, b_i, r)$. Store this and - $d_i$ as the new state. + \item In the initial state $\mathsf{initial}$, read $\alph_0 = \langle p_0, + a_0, q_0, d_0 \rangle$, set the state to $\langle q, d_0 \rangle$. + \item Now when reading letter $\alpha_i = \langle p_i, a_i, q_i, d_i + \rangle$ in state $\langle r, d \rangle$, if $d$ if $\leftsymbol$, use + $A$'s transition function $\delta$ to compute the new tree state as + $\delta(r, a_i, q_i)$ (the previously computed tree state is of our left + child's, and our right child's comes from the current letter). If $d$ is + $\rightsymbol$, the new tree state will instead be $\delta(p_i, a_i, + r)$. Store this and $d_i$ as the new state. \item Accept if the final tree state is $q'$. \end{enumerate} |