From e9fa1cc91cb8056f2a530c9cac57cd76f5f98022 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Sat, 7 Jul 2018 00:01:15 +0100 Subject: [PATCH] Paper: some tweaks for the examples of traces computation. --- re2c/doc/tdfa_v2/TODO | 60 ++++++++++++ re2c/doc/tdfa_v2/img/pe.tex | 150 +++++++++++++++++----------- re2c/doc/tdfa_v2/img/pe2.tex | 162 ++++++++++++++++++++++++------- re2c/doc/tdfa_v2/part_1_tnfa.tex | 8 +- 4 files changed, 286 insertions(+), 94 deletions(-) diff --git a/re2c/doc/tdfa_v2/TODO b/re2c/doc/tdfa_v2/TODO index b5e7030f..6f5e5b34 100644 --- a/re2c/doc/tdfa_v2/TODO +++ b/re2c/doc/tdfa_v2/TODO @@ -70,3 +70,63 @@ be delivered. What I mean is that our algorithm can do it, and this is more general than Posix subexpressions. Indeed, it can go from full-parsing to any user-defined submatch extraction. +- Definition 17: F is used both to denote the set of final states and the function defined in Figure 2. + Perhaps it could be better to use two letters? + +- Figure 2, + - first graph: in it F(i,j,r) is defined for i != 0. However, an F with a first argument that is not zero is + never used. Perhaps there is a need to give some explanation + - graph for alternative: why the tags are defined only in the incoming arc of the second term, and the ougoing of the first? + +- in Figure 3: + - in match(), closure is called with a first argument that should +be the set containing the initial + configuration, that in the call is a 4-tuple. However, closure +expects configurations as 2-ples. + - in the first configuration there is a t_0 that is not defined + - reach() is called with three arguments, while in its definition +it has two. I think that its signature + should be reach(X,Delta,alpha). + Configurations are 4-ples: (origin-state, target-state, +input-symbol, tag), correct? The origin-state + is there for precedence(), and was the 'origin' in the pseudocode. + +- in Figure 4, closure_goldberg_radzik should be closure, and it +should handle 4-ples configurations. +Figure 4: + + - relax. At the beginning all the values of result() are _|_, thus +relax() should take care of it. + I suggest to replace the first two lines with: + + if relax = _|_ or precedence(x,result(q),B,D then + + - closure_goldberg_radzik, 2nd and 3rd lines: here result and status +are initialized for all the states. + To prevent some reviewer to point out that "q" is not defined, I +suggest to enclose the two + statements in a foreach q in Q + - same, line 14: here scan() is called, which in turn calls relax(), +which accesses "status". Thus, + "status" should be passed as argument to both + + - relax: its signature has B and D as last 5th and 6th arguments, but +they are never passed when called. + They should be passed all along closure_goldberg_radzik and scan. + + Comparing it with calc_rho_prec() in the pseudocode: + - the first two "if" statements can be merged + - the statement: h_1 = h_2 = height(...) can only be executed if k > +1 (otherwise it accesses a_0 ...) + - the statement: "if a_k > b_k then l = -1" and the following, are +different from the ones in the + pseudocode (if nonnegative (a[i]) return LT, etc.) + Comparing it with update_rho in the pseudocode: + - the pseudocode initializes h_1 and h_2 with the values read from +B, while here it does so when + k > 1, which is never the case when q_1 != q_2 + + +- the statement: "if a_k > b_k then l = -1" and the following, are + different from the ones in the pseudocode (if nonnegative (a[i]) return LT, etc.) + diff --git a/re2c/doc/tdfa_v2/img/pe.tex b/re2c/doc/tdfa_v2/img/pe.tex index 8980859b..d0fedf1f 100644 --- a/re2c/doc/tdfa_v2/img/pe.tex +++ b/re2c/doc/tdfa_v2/img/pe.tex @@ -30,8 +30,9 @@ \begin{scope}[xshift=0in, yshift=0in] \node (a) {{ $\begin{aligned} - \quad\quad - & \Phi_0 \big( + &\alpha + = \Phi_0 (s) + = \Phi_0 \big( {T}^{1} ( {T}^{2} ( {\varnothing}^{0}, @@ -39,22 +40,15 @@ ), {T}^{3}( {\varnothing}^{4} ) - )\big) &&= - \Xl_1 - \Xl_2 - a - \Xr_1 - \Xl_2 - \Xm_2 - \Xr_1 - \Xr_0 - &&= \overbracket {\Xl_1 \Xl_2 }%^{\alpha_0} - && a - && \overbracket { \Xr_1 \Xl_2 \Xm_2 \Xr_1 \Xr_0 }%^{\alpha_1} -% &&= \alpha_0 a \alpha_1 - &&= \alpha + )\big) + &&\!\!\!\!=\; + \overbracket {\Xl_1 \Xl_2 }%^{\alpha_0} + \;a\; + \overbracket { \Xr_1 \Xl_2 \Xm_2 \Xr_1 \Xr_0 }%^{\alpha_1} \\[-0.4em] - & \Phi_0 \big( + &\beta + = \Phi_0 (t) + = \Phi_0 \big( {T}^{1} ( {T}^{2}( {\varnothing}^{0}, @@ -63,23 +57,15 @@ {T}^{3}\big( {T}^{4}({a}^{0},{\varnothing}^{0}) ) - )\big) &&= - \Xl_1 - \Xl_2 - \Xr_1 - \Xl_2 - \Xl_3 - a - \Xr_2 - \Xr_1 - \Xr_0 - &&= \overbracket { \Xl_1 \Xl_2 \Xr_1 \Xl_2 \Xl_3 }%^{\beta_0} - && a - && \overbracket { \Xr_2 \Xr_1 \Xr_0 }%^{\beta_1} -% &&= \beta_0 a \beta_1 - &&= \beta + )\big) + &&\!\!\!\!=\; + \overbracket { \Xl_1 \Xl_2 \Xr_1 \Xl_2 \Xl_3 }%^{\beta_0} + \;a\; + \overbracket { \Xr_2 \Xr_1 \Xr_0 }%^{\beta_1} \\[-0.4em] - & \Phi_0 \big( + &\gamma + = \Phi_0 (u) + = \Phi_0 \big( {T}^{1} ( {T}^{2}( {\epsilon}^{0}, @@ -89,29 +75,19 @@ {T}^{4}({a}^{0},{\varnothing}^{0}), {T}^{4}({\varnothing}^{0}, {\epsilon}^{0}) ) - )\big) &&= - \Xl_1 - \Xl_2 - \Xr_1 - \Xl_2 - \Xl_3 - a - \Xr_2 - \Xl_3 - \Xr_2 - \Xr_1 - \Xr_0 - &&= \overbracket { \Xl_1 \Xl_2 \Xr_1 \Xl_2 \Xl_3 }%^{\gamma_0} - && a - && \overbracket { \Xr_2 \Xl_3 \Xr_2 \Xr_1 \Xr_0 }%^{\gamma_1} -% &&= \gamma_0 a \gamma_1 - &&= \gamma - \quad\quad + )\big) + &&\!\!\!\!=\; + \overbracket { \Xl_1 \Xl_2 \Xr_1 \Xl_2 \Xl_3 }%^{\gamma_0} + \;a\; + \overbracket { \Xr_2 \Xl_3 \Xr_2 \Xr_1 \Xr_0 }%^{\gamma_1} \end{aligned}$ }}; \end{scope} -\begin{scope}[xshift=0in, yshift=-1.7in] +\setlength\tabcolsep{3pt} +%\renewcommand{\arraystretch}{1.1} + +\begin{scope}[xshift=0in, yshift=-1.75in] \node (a) { $\begin{aligned} &\begin{tabular}{c|ll} @@ -127,7 +103,7 @@ \rho_1 &= min (\rho_0, minh (\Xr_1 \Xl_2 \Xm_2 \Xr_1 \Xr_0)) = min (2,0) = 0 \\[-0.3em] \rho'_1 &= min (\rho'_0, minh (\Xr_2 \Xr_1 \Xr_0)) = min (1,0) = 0 \end{aligned}\right. - \\[0.5em] + \\[0.7em] &\begin{tabular}{c|ll} $traces (\beta, \gamma)$ & 0 & 1 \\ \hline \\[-1em] @@ -141,7 +117,7 @@ \rho_1 &= min (lasth (\Xr_2), minh (\Xr_1 \Xr_0)) = min (2,0) = 0 \\[-0.3em] \rho'_1 &= min (lasth (\Xr_2), minh (\Xl_3 \Xr_2 \Xr_1 \Xr_0)) = min (2,0) = 0 \end{aligned}\right. - \\[0.5em] + \\[0.7em] &\begin{tabular}{c|ll} $traces (\alpha, \gamma)$ & 0 & 1 \\ \hline \\[-1em] @@ -159,6 +135,72 @@ }; \end{scope} + + +\tikzstyle{every node}=[draw=none, shape=rectangle, sibling distance=0, level distance=0, outer sep = 0] + +\small{ +\begin{scope}[xshift=-3.5in, yshift=0.3in] + \node[xshift=-0.2in, draw=none] {$s:$}; + \graph [tree layout, grow=down, fresh nodes] { + "${T}^{1}$" -- { + "${T}^{2}$" -- { + "${\varnothing}^{0}$"[draw=none], + "${T}^{0}$"[draw=none] -- { + "${a}^{0}$"[draw=none] + } + }, + "${T}^{3}$" -- { + "${\varnothing}^{4}$" + } + } + }; +\end{scope} + +\begin{scope}[xshift=-3.5in, yshift=-0.85in] + \node[xshift=-0.2in, draw=none] {$t:$}; + \graph [tree layout, grow=down, fresh nodes] { + "${T}^{1}$" -- { + "${T}^{2}$" -- { + "${\varnothing}^{0}$"[draw=none], + "${T}^{0}$"[draw=none] -- { + "${\varnothing}^{0}$"[draw=none] + } + }, + "${T}^{3}$" -- { + "${T}^{4}$" -- { + "${a}^{0}$"[draw=none], + "${\varnothing}^{0}$"[draw=none] + } + } + } + }; +\end{scope} + +\begin{scope}[xshift=-3.5in, yshift=-2in] + \node[xshift=-0.2in, draw=none] {$u:$}; + \graph [tree layout, grow=down, fresh nodes] { + "${T}^{1}$" -- { + "${T}^{2}$" -- { + "${\epsilon}^{0}$"[draw=none], + "${\varnothing}^{0}$"[draw=none] + }, + "${T}^{3}$" -- { + "${T}^{4}$" -- { + "${a}^{0}$"[draw=none], + "${\varnothing}^{0}$"[draw=none] + }, + "${T}^{4}$" -- { + "${\varnothing}^{0}$"[draw=none], + "${\epsilon}^{0}$"[draw=none] + } + } + } + }; +\end{scope} +} + + \end{tikzpicture} \end{document} diff --git a/re2c/doc/tdfa_v2/img/pe2.tex b/re2c/doc/tdfa_v2/img/pe2.tex index 9be68fcc..22bd32f7 100644 --- a/re2c/doc/tdfa_v2/img/pe2.tex +++ b/re2c/doc/tdfa_v2/img/pe2.tex @@ -21,37 +21,37 @@ \begin{document} -\begin{tikzpicture}[>=stealth, ->, auto, sibling distance = 0.3in, inner sep = 1.5pt] +\begin{tikzpicture}[>=stealth, auto, sibling distance = 0.3in, inner sep = 1.5pt] \tikzstyle{every node}=[draw, shape = circle] \begin{scope}[xshift=0in, yshift=0in] \graph [tree layout, grow=down, fresh nodes] { - "$1$"[draw] -- { + "$t_1$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$", "$a$", "$a$" } } } - , "$2$"[draw] -- { + , "$t_2$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$", "$a$" }, ""[draw] -- { "$a$" } } } - , "$3$"[draw] -- { + , "$t_3$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$" }, ""[draw] -- { "$a$", "$a$" } } } - , "$4$"[draw] -- { + , "$t_4$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$" }, ""[draw] -- { "$a$" }, ""[draw] -- { "$a$" } } } - , "$5$"[draw] -- { + , "$t_5$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$", "$a$" } }, @@ -59,7 +59,7 @@ ""[draw] -- { "$a$" } } } - , "$6$"[draw] -- { + , "$t_6$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$" } }, @@ -67,7 +67,7 @@ ""[draw] -- { "$a$", "$a$" } } } - , "$7$"[draw] -- { + , "$t_7$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$"}, ""[draw] -- { "$a$"} @@ -76,7 +76,7 @@ ""[draw] -- { "$a$" } } } - , "$8$"[draw] -- { + , "$t_8$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$"} }, @@ -85,7 +85,7 @@ ""[draw] -- { "$a$" } } } - , "$9$"[draw] -- { + , "$t_9$"[draw] -- { ""[draw] -- { ""[draw] -- { "$a$" } }, @@ -99,11 +99,97 @@ }; \end{scope} -\begin{scope}[xshift=1in, yshift=0in] - \draw [dash pattern = on 2pt off 2pt, rounded corners] (2,-0.3) -- (2,-1) -- (1.45,-1.9) -- (1.45,-2.75); - \draw [dash pattern = on 2pt off 2pt, rounded corners] (1.75,-2.75) -- (1.75,-2) -- (2.2,-1.3) -- (2.6,-2) -- (2.3,-2.75); - \draw [dash pattern = on 2pt off 2pt, rounded corners] (2.55,-2.8) -- (2.75,-2.3) -- (2.9,-2.8); - \draw [dash pattern = on 2pt off 2pt, rounded corners] (3.2,-2.75) -- (2.9,-1.9) -- (2.35,-1) -- (2.35,-0.3); +\tikzstyle{styleD}=[rounded corners, thick, dash pattern=on 1pt off 3pt] +\tikzstyle{styleC}=[rounded corners, thick, dash pattern=on 3pt off 2pt] +\tikzstyle{styleB}=[rounded corners, thick, dash pattern=on 5pt off 2pt] +\tikzstyle{styleA}=[rounded corners, thick, dash pattern=on 8pt off 2pt] + +\begin{scope}[xshift=0in, yshift=-3.35in] +% \tikzstyle{every node}=[draw, shape=circle] + \tikzstyle{every node}=[draw=none, shape=rectangle, inner sep = 0, level distance=0.45in] + \graph [tree layout, grow=down, fresh nodes, sibling distance=0.45in] { + a1/""[label=above:$t_3$]{} -- { + a11/"" -- { + a111/"" -- { a1111/""[label=below:$a$] }, + a112/"" -- { a1121/""[label=below:$a$], a1122/""[label=below:$a$] } + } + } + }; + \tikzstyle{every node}=[draw=none, shape=rectangle] + \newcommand\e{1.3em} + \node (x1) at (a1) {$\Xl_1 \hspace{\e} \Xr_0$}; + \node (x11) at (a11) {$\Xl_2 \hspace{\e} \Xr_1$}; + \node (x111) at (a111) {$\Xl_3 \hspace{\e} \Xr_2$}; + \node (x112) at (a112) {$\Xl_3 \hspace{\e} \Xr_2$}; + \node (x1111) at (a1111) {$\Xl_4 \hspace{\e} \Xr_3$}; + \node (x1121) at (a1121) {$\Xl_4 \hspace{\e} \Xr_3$}; + \node (x1122) at (a1122) {$\Xl_4 \hspace{\e} \Xr_3$}; + + \newcommand\xxx{ + \tikzstyle{every node}=[outer sep=0] + \newcommand\w{0.12} + \draw [->, styleA, lightgray, very thick] ($(a1.center)+(-\w,0)$) -- ($(a11.center)+(-\w,0)$) -- ($(a111.center)+(-\w,0)$) -- ($(a1111.center)+(-\w,0)$); + \draw [ styleB, lightgray, very thick] ($(a1111.center)+(\w,0)$) -- ($(a111.center)+(\w,0)$); + \draw [->, styleB] ($(a111.center)+(\w,0)$) -- ($(a11.center)+(0,-0.18)$) -- ($(a112.center)+(-\w,0)$) -- ($(a1121)+(-\w,0)$); + \draw [->, styleC] ($(a1121.center)+(\w,0)$) -- ($(a112.center)+(0,-0.18)$) -- ($(a1122.center)+(-\w,0)$); + \draw [->, styleD] ($(a1122.center)+(\w,0)$) -- ($(a112.center)+(\w,0)$) -- ($(a11.center)+(\w,0)$) -- ($(a1.center)+(\w,0)$); + } + \xxx + +% \node (f) [draw, shape=ellipse, fill] at ($(a111.center)+(\w,0)$) {}; +\end{scope} + +\begin{scope}[xshift=1.65in, yshift=-3.35in] +% \tikzstyle{every node}=[draw, shape=circle] + \tikzstyle{every node}=[draw=none, shape=rectangle, inner sep = 0, level distance=0.45in] + \graph [tree layout, grow=down, fresh nodes, sibling distance=0.45in] { + b1/""[label=above:$t_5$]{} -- { + b11/"" -- { + b111/"" -- { b1111/""[label=below:$a$]{}, b1112/""[label=below:$a$] } + }, + b12/"" -- { + b121/"" -- { b1211/""[label=below:$a$] } + } + } + }; + \tikzstyle{every node}=[draw=none, shape=rectangle] + \newcommand\e{1.3em} + \node (y1) at (b1) {$\Xl_1 \hspace{\e} \Xr_0$}; + \node (y11) at (b11) {$\Xl_2 \hspace{\e} \Xr_1$}; + \node (y12) at (b12) {$\Xl_2 \hspace{\e} \Xr_1$}; + \node (y111) at (b111) {$\Xl_3 \hspace{\e} \Xr_2$}; + \node (y121) at (b121) {$\Xl_3 \hspace{\e} \Xr_2$}; + \node (y1111) at (b1111) {$\Xl_4 \hspace{\e} \Xr_3$}; + \node (y1112) at (b1112) {$\Xl_4 \hspace{\e} \Xr_3$}; + \node (y1211) at (b1211) {$\Xl_4 \hspace{\e} \Xr_3$}; + + \newcommand\yyy{ + \tikzstyle{every node}=[outer sep=0] + \newcommand\w{0.12} + \draw [->, lightgray, very thick, styleA] ($(b1.center)+(-\w,0)$) -- ($(b11.center)+(-\w,0)$) -- ($(b111.center)+(-\w,0)$) -- ($(b1111.center)+(-\w,0)$); + \draw [ lightgray, very thick, styleB] ($(b1111.center)+(\w,0)$) -- ($(b111.center)+(0,-0.18)$); + \draw [->, styleB] ($(b111.center)+(0,-0.18)$) -- ($(b1112.center)+(-\w,0)$); + \draw [->, styleC] ($(b1112.center)+(\w,0)$) -- ($(b111.center)+(\w,0)$) -- ($(b11.center)+(\w,0)$) -- ($(b1.center)+(0,-0.18)$) + -- ($(b12.center)+(-\w,0)$) -- ($(b121.center)+(-\w,0)$) -- ($(b1211.center)+(-\w,0)$); + \draw [->, styleD] ($(b1211.center)+(\w,0)$) -- ($(b121.center)+(\w,0)$) -- ($(b12.center)+(\w,0)$) -- ($(b1.center)+(\w,0)$); + } + \yyy + +% \node (f) [draw, shape=ellipse, fill] at ($(b111.center)+(0,-0.25)$) {}; +\end{scope} + +\begin{scope}[xshift=2.8in, yshift=-4.95in] + \tikzstyle{every node}=[draw=none, shape=rectangle] + \newcommand\z{0.3} + \node (a1) at (0,0) {}; + \node at ($(a1)+(0,5*\z)$) [label=left:{{frame 0}}]{}; + \draw[->, styleA] ($(a1)+(0,5*\z)+(0,0)$) -- ($(a1)+(0,5*\z)+(1.2,0)$); + \node at ($(a1)+(0,4*\z)$) [label=left:{{frame 1}}]{}; + \draw[->, styleB] ($(a1)+(0,4*\z)+(0,0)$) -- ($(a1)+(0,4*\z)+(1.2,0)$); + \node at ($(a1)+(0,3*\z)$) [label=left:{{frame 2}}]{}; + \draw[->, styleC] ($(a1)+(0,3*\z)+(0,0)$) -- ($(a1)+(0,3*\z)+(1.2,0)$); + \node at ($(a1)+(0,2*\z)$) [label=left:{{frame 3}}]{}; + \draw[->, styleD] ($(a1)+(0,2*\z)+(0,0)$) -- ($(a1)+(0,2*\z)+(1.2,0)$); \end{scope} %\begin{scope}[xshift=0in, yshift=0.1in] @@ -114,29 +200,33 @@ % \node [right of = a4, xshift = 0.45in] (a5) {5}; %\end{scope} -\begin{scope}[xshift=6.5in, yshift=-3.1in] +\begin{scope}[xshift=6.7in, yshift=-3.2in] \node [shape=rectangle, draw = none] (a) { $\begin{aligned} - &1 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &2 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &3 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &4 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &5 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &6 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &7 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &8 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ - &9 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} + &\begin{aligned} + &t_1 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_2 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_3 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_4 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_5 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_6 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_7 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_8 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} \\ + &t_9 &&\overbracket {\Xl_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xl_2 \Xl_3 \Xl_4} a \overbracket {\Xr_3 \Xr_2 \Xr_1 \Xr_0} + \end{aligned} + \\[1em] + & \quad\quad t_1 < t_2 < t_3 < t_4 < t_5 < t_7 < t_6 < t_8 < t_9 \end{aligned}$ }; \end{scope} -\begin{scope}[xshift=2.2in, yshift=-3.1in] +\begin{scope}[xshift=2.4in, yshift=-3.1in] \node [shape=rectangle, draw = none] (a) { \setlength\tabcolsep{2pt} \renewcommand{\arraystretch}{1.1} $\begin{aligned} &\begin{tabular}{c ccccccccc} - 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ + $t_2$ & $t_3$ & $t_4$ & $t_5$ & $t_6$ & $t_7$ & $t_8$ & $t_9$ \\ % \begin{tabular}{|cccc|} \hline @@ -193,7 +283,7 @@ -1 & 1 & 1 & 0 \\ \hline \end{tabular} - & 1 + & $t_1$ \\[1em] % & @@ -245,7 +335,7 @@ -1 & 1 & 1 & 0 \\ \hline \end{tabular} - & 2 + & $t_2$ \\[1em] % & & @@ -256,12 +346,14 @@ \hline \end{tabular} & + \bf{ \begin{tabular}{|cccc|} \hline -1 & 2 & 2 & 0 \\[-3pt] -1 & 3 & 1 & 0 \\ \hline \end{tabular} + } & \begin{tabular}{|cccc|} \hline @@ -290,7 +382,7 @@ -1 & 1 & 1 & 0 \\ \hline \end{tabular} - & 3 + & $t_3$ \\[1em] % & & & @@ -328,7 +420,7 @@ -1 & 1 & 1 & 0 \\ \hline \end{tabular} - & 4 + & $t_4$ \\[1em] % & & & & @@ -359,7 +451,7 @@ -1 & 1 & 1 & 0 \\ \hline \end{tabular} - & 5 + & $t_5$ \\[1em] % & & & & & @@ -383,7 +475,7 @@ -1 & \!-1 & 1 & 0 \\ \hline \end{tabular} - & 6 + & $t_6$ \\[1em] % & & & & & & @@ -400,7 +492,7 @@ -1 & 1 & 1 & 0 \\ \hline \end{tabular} - & 7 + & $t_7$ \\[1em] % & & & & & & & @@ -410,7 +502,7 @@ -1 & \!-1 & 1 & 0 \\ \hline \end{tabular} - & 8 + & $t_8$ \end{tabular} \end{aligned}$ }; diff --git a/re2c/doc/tdfa_v2/part_1_tnfa.tex b/re2c/doc/tdfa_v2/part_1_tnfa.tex index b1df341d..b7e82b3c 100644 --- a/re2c/doc/tdfa_v2/part_1_tnfa.tex +++ b/re2c/doc/tdfa_v2/part_1_tnfa.tex @@ -735,11 +735,9 @@ Therefore $\alpha < \beta < \gamma$. \begin{figure}\label{fig_pe2} \includegraphics[width=\linewidth]{img/pe2.pdf} \caption{ -An example of PEs for IPTs from figure \ref{fig_mark_enum} and the computation of $traces$ for each pair of PEs.\\ -Here $\alpha \sqsubset \beta$ and $\alpha \sqsubset \gamma$, while -$\beta \sim \gamma$ and $\beta \subset \gamma$, -because $first (\beta \backslash \gamma) = \Xr < \Xl = first (\gamma \backslash \beta)$. -Therefore $\alpha < \beta < \gamma$. +An example of all possible IPTs for RE $((a^{1,3})^{1,3})^{1,3}$ and string $aaa$, the corresponding PEs\\ +and the table of their pairwise traces. +IPTs $t_3$ and $t_5$ are showed in more detail below. } \end{figure} -- 2.40.0