From 75a45812e08031e77b6bca43adf4ed4547b61a31 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Tue, 18 Dec 2018 23:56:04 +0000 Subject: [PATCH] Paper: tweaked TNFA construction. --- re2c/doc/tdfa_v2/img/tnfa_construction.tex | 65 ++++++------ re2c/doc/tdfa_v2/img/tnfa_example.tex | 56 ++++++----- re2c/doc/tdfa_v2/part_1_tnfa.tex | 110 ++++++++++----------- 3 files changed, 119 insertions(+), 112 deletions(-) diff --git a/re2c/doc/tdfa_v2/img/tnfa_construction.tex b/re2c/doc/tdfa_v2/img/tnfa_construction.tex index e900bc94..b4223c7d 100644 --- a/re2c/doc/tdfa_v2/img/tnfa_construction.tex +++ b/re2c/doc/tdfa_v2/img/tnfa_construction.tex @@ -36,7 +36,7 @@ \begin{scope}[xshift=0in, yshift=0in] \begin{scope}[xshift=0in, yshift=0in] - \node[draw=none] (a) {$\hphantom{\hspace{2in}}$}; + \node[draw=none] (a) {$\hphantom{\hspace{1in}}$}; \end{scope} \begin{scope}[xshift=0in, yshift=0in] @@ -55,34 +55,34 @@ $\retonfa \big( (0, 0, a), y \big) $}] (a) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-1.5in] +\begin{scope}[xshift=0in, yshift=-1.4in] \def\offs{-0.5in} \def\widd{1.3in} \node[state] (a1) {$z$}; - \node[style1, right of = a1] (a) {$F(r_1)$}; + \node[style1, right of = a1] (a) {$F(s)$}; \node[style2, right of = a] (a2) {$x$}; - \node[style1, right of = a2] (b) {$F(r_2)$}; + \node[style1, right of = a2] (b) {$F(u)$}; \node[style2, right of = b] (b2) {$y$}; \node [label={[label distance=0.2in, below left]270:\large{(c)}}] (a) {}; \node [label={[label distance=0.2in, below right]270: - $\retonfa \big( (0, 0, r_1 \cdot r_2), y \big) $}] (a1) {}; + $\retonfa \big( (0, 0, s \cdot u), y \big) $}] (a1) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-2.8in] +\begin{scope}[xshift=0in, yshift=-2.6in] \def\offs{-0.5in} \def\widd{1.3in} \node[state] (a) {$x$}; \node[state, above right of = a, yshift = -0.35in] (b1) {$x_2$}; - \node[style1, right of = b1] (b) {$F(r_1)$}; + \node[style1, right of = b1] (b) {$F(s)$}; \node[style2, right of = b] (b2) {$x_1$}; - \node[style1, right of = b2, rotate around={-21:(b2)}] (d) {$N(r_2)$}; + \node[style1, right of = b2, rotate around={-21:(b2)}] (d) {$N(u)$}; \node[state, below right of=a, yshift = 0.35in] (c1) {$x_4$}; - \node[style1, right of = c1] (c2) {$N(r_1)$}; + \node[style1, right of = c1] (c2) {$N(s)$}; \node[style2, right of = c2] (c3) {$x_3$}; - \node[style1, right of = c3, rotate around={21:(c3)}] (c) {$F(r_2)$}; + \node[style1, right of = c3, rotate around={21:(c3)}] (c) {$F(u)$}; \node[style2, right of = c, rotate around={21:(c)}] (d) {$y$}; \path (a) edge [bend left] node {$1 / \epsilon$} (b1) @@ -90,10 +90,10 @@ ; \node [label={[label distance=0.5in, below left]270:\large{(d)}}] (a) {}; \node [label={[label distance=0.5in, below right]270: - $\retonfa \big( (0, 0, r_1 \mid r_2), y \big) $}] (a) {}; + $\retonfa \big( (0, 0, s \mid u), y \big) $}] (a) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-4in] +\begin{scope}[xshift=0in, yshift=-3.8in] \def\offs{-0.5in} \def\widd{1.3in} @@ -107,7 +107,7 @@ $\retonfa \big( (0, 0, r^{n, m}), y \big) \mid_{n \;>\; 1} $}] (a1) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-5.2in] +\begin{scope}[xshift=0in, yshift=-5in] \def\offs{-0.5in} \def\widd{1.3in} @@ -127,7 +127,7 @@ $\retonfa \big( (0, 0, r^{0, m}), y \big) $}] (a) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-6.8in] +\begin{scope}[xshift=0in, yshift=-6.6in] \def\offs{-0.5in} \def\widd{1.3in} @@ -146,7 +146,7 @@ $\retonfa \big( (0, 0, r^{1, \infty}), y \big) $}] (b1) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-7.75in] +\begin{scope}[xshift=0in, yshift=-7.4in] \def\offs{-0.5in} \def\widd{1.3in} @@ -159,7 +159,7 @@ $\retonfa \big( (0, 0, r^{1, 1}), y \big) $}] (b1) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-9in] +\begin{scope}[xshift=0in, yshift=-8.6in] \def\offs{-0.5in} \def\widd{1.3in} @@ -180,7 +180,7 @@ $\retonfa \big( (0, 0, r^{1, m}), y \big) \mid_{1 < m < \infty} $}] (b1) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-10.5in] +\begin{scope}[xshift=0in, yshift=-10in] \def\offs{-0.5in} \def\widd{1.3in} @@ -198,28 +198,27 @@ $\retonfa \big( (i, \Xund, r) \big) \mid_{i \;\neq\; 0} $}] (a) {}; \end{scope} -\begin{scope}[xshift=0in, yshift=-11.2in] +\begin{scope}[xshift=0in, yshift=-10.8in] \def\offs{-0.5in} \def\widd{1.3in} - \node[state, accepting] (a) {$y$}; - \node [label={[label distance=0.1in, below left]270:\large{(j)}}] (a) {}; - \node [label={[label distance=0.1in, below right]270: - $\ntag \big( (0, \Xund, \Xund) \big) $}] (a) {}; -\end{scope} - -\begin{scope}[xshift=0in, yshift=-12in] - \def\offs{-0.5in} - \def\widd{1.3in} - - \node[state] (a) {$x$}; - \node[state, accepting, right of = a] (a1) {$y$}; + \node[state] (a) {$x_0$}; + \node[state, right of = a] (a1) {$x_1$}; + \node[state, right of = a1] (b1) {$x_2$}; + \node[draw=none, right of = b1, xshift=-0.5in] (b) {\large{$\dots$}}; + \node[state, accepting, right of = b, xshift=-0.5in] (b2) {$x_{2n}$}; \path - (a) edge node {$1 / 1 -\! 2i $} (a1) + (a) edge node {$1 / -\!(2i-1) $} (a1) + (a1) edge node {$1 / -\! 2i $} (b1) + (b1) edge node {} (b) + (b) edge node {} (b2) ; - \node [label={[label distance=0.1in, below left]270:\large{(k)}}] (a) {}; + \node [label={[label distance=0.1in, below left]270:\large{(j)}}] (a) {}; \node [label={[label distance=0.1in, below right]270: - $\ntag \big( (i, \Xund, r) \big) \mid_{i \;\neq\; 0} $}] (a) {}; + $\begin{aligned} + N \big( (i, \Xund, r) \big) + \end{aligned}$ + }] (a) {}; \end{scope} \end{scope} diff --git a/re2c/doc/tdfa_v2/img/tnfa_example.tex b/re2c/doc/tdfa_v2/img/tnfa_example.tex index 08bbed66..db243066 100644 --- a/re2c/doc/tdfa_v2/img/tnfa_example.tex +++ b/re2c/doc/tdfa_v2/img/tnfa_example.tex @@ -20,9 +20,9 @@ \tikzstyle{every node}=[] \tikzstyle{every state}=[circle - , minimum size=0.15in + , minimum size=0.16in , rectangle - , rounded corners=4 + , rounded corners=5 , inner sep = 2pt , outer sep = 0pt , node distance = 0.4in] @@ -30,8 +30,8 @@ \newcommand{\zz}{0.06in} \begin{scope}[xshift=-0.8in, yshift=-10.5in] - \footnotesize - %\scriptsize + %\footnotesize + \scriptsize % ((epsilon|a*)((a|epsilon){0,3})) @@ -47,6 +47,7 @@ \node[state, below right of = x21] (x22) {$8$}; \node[state, right of = x1, xshift=0.6in] (z1) {$18$}; + \node[state, right of = z1, xshift=0.27in] (z2) {$19$}; \node[state, right of = x22] (y15) {$9$}; \node[state, above right of = y15] (y16) {$10$}; @@ -58,27 +59,29 @@ \node[state, above right of = z15] (z16) {$15$}; \node[state, fill=lightgray, above right of = z16, xshift = \zz, yshift = -\zz] (z17) {$16$}; \node[state, below right of = z17, xshift = \zz, yshift = +\zz] (z21) {$17$}; - \node[state, below right of = z21] (z22) {$19$}; + \node[state, below right of = z21] (z22) {$20$}; - \node[state, below right of = z22] (x23) {$20$}; + \node[state, below right of = z22] (x23) {$21$}; - \node[state, above right of = x23] (x2) {$21$}; - \node[state, above right of = x2, xshift = \zz, yshift = -\zz] (x4X) {$22$}; - \node[state, above right of = x4X] (x4) {$23$}; + \node[state, above right of = x23] (x2) {$22$}; + \node[state, above right of = x2, xshift = \zz, yshift = -\zz] (x4X) {$23$}; + \node[state, above right of = x4X] (x4) {$24$}; - \node[state, below right of = x2, xshift = \zz+0.1in, yshift = +\zz] (x3) {$28$}; - \node[state, right of = x3, xshift=0.1in] (x3Z) {$29$}; - \node[state, above right of = x3Z] (x3X) {$30$}; + \node[state, below right of = x2, xshift = \zz+0.1in, yshift = +\zz] (x3) {$30$}; + \node[state, right of = x3, xshift=0.1in] (x3Y) {$31$}; + \node[state, right of = x3Y, xshift=0.1in] (x3Z) {$32$}; + \node[state, above right of = x3Z] (x3X) {$33$}; \node[state, below right of = x3X, draw=none, inner sep=0, minimum size=0] (x3W) {}; - \node[state, fill=lightgray, above right of = x4, xshift = \zz, yshift = -\zz] (x5) {$24$}; - \node[state, right of = x5] (x6) {$25$}; - \node[state, below right of = x6, xshift = \zz, yshift = \zz] (x7) {$26$}; - \node[state, below right of = x7] (x7Y) {$27$}; - \node[state, below right of = x7Y, xshift = \zz, yshift = +\zz] (x12) {$31$}; - \node[state, below right of = x12] (x14) {$32$}; + \node[state, fill=lightgray, above right of = x4, xshift = \zz, yshift = -\zz] (x5) {$25$}; + \node[state, right of = x5] (x6) {$26$}; + \node[state, below right of = x6, xshift = \zz, yshift = \zz] (x7) {$27$}; + \node[state, below right of = x7] (x7X) {$28$}; + \node[state, right of = x7X] (x7Y) {$29$}; + \node[state, below right of = x7Y, xshift = \zz, yshift = +\zz] (x12) {$34$}; + \node[state, below right of = x12] (x14) {$35$}; - \node[state, fill=lightgray, accepting, below right of = x14] (x24) {$33$}; + \node[state, fill=lightgray, accepting, below right of = x14] (x24) {$36$}; \path (x0) edge node [above left] {$1/1$} (x1) @@ -86,6 +89,7 @@ (z0) edge node {$1/\epsilon$} (x15) (z0) edge [bend right=20] node [above, near end] {$2/\epsilon$} (z1) + (z1) edge node [below] {$1/\!\!-\!\!5$} (z2) (x15) edge node [above left] {$1/5$} (x16) (x16) edge [bend left] node [above] {$1/\epsilon$} (x17) @@ -114,15 +118,17 @@ (x23) edge node [below right] {$1/7$} (x2) (x2) edge [bend left] node [above] {$1/\epsilon$} (x4X) (x2) edge [bend right] node [above] {$\quad 2/\epsilon$} (x3) - (x3) edge node [above] {$2/\!\!-\!\!9$} (x3Z) - (x3Z) edge node [below right] {$1/11$} (x3X) + (x3) edge node [below] {$2/\!\!-\!\!9$} (x3Y) + (x3Y) edge node [below] {$2/\!\!-\!\!10$} (x3Z) + (x3Z) edge node [above left] {$1/11$} (x3X) (x4X) edge node {$1/9$} (x4) (x4) edge [bend left] node [above] {$1/\epsilon$} (x5) (x4) edge [bend right=20] node [above] {$2/\epsilon$} (x7) (x5) edge node [above] {$a/\epsilon$} (x6) (x6) edge [bend left] node [above] {$2/\epsilon$} (x7) - (x7) edge node {$1/10$} (x7Y) - (x7Y) edge [bend left] node {$1/\!\!-\!\!11$} (x12) + (x7) edge node {$1/10$} (x7X) + (x7X) edge node {$1/\!\!-\!\!11$} (x7Y) + (x7Y) edge [bend left] node {$1/\!\!-\!\!12$} (x12) (x12) edge node [above right] {$1/8$} (x14) (x14) edge node [above right] {$1/2$} (x24) @@ -130,8 +136,10 @@ \draw (y22) .. controls ($ (y22) + (0.5, -0.6) $) and ($ (z22) + (-0.5, -0.6) $) .. node [above] {$1/\epsilon$} (z22); \draw (x22) .. controls ($ (x22) + (0.8, -0.8) $) and ($ (z22) + (-0.8, -0.8) $) .. node [above, near start] {$1/\epsilon$} (z22); - \draw (z1) .. controls ($ (z1) + (2, 0) $) and ($ (z22) + (-1.0, -1.0) $) .. node [above, very near start] {$1/\!\!-\!\!5$} (z22); + \draw (z2) .. controls ($ (z2) + (2, 0) $) and ($ (z22) + (-1.0, -1.0) $) .. node [below, very near start] {$1/\!\!-\!\!6$} (z22); \draw (x6) .. controls ($ (x6) + (0.3, 0.8) $) and ($ (x5) + (-0.3, 0.8) $) .. node [above] {$1/\epsilon$} (x5); + +% \draw (x3X) .. controls ($ (x3X) + (0.9, -0.9) $) and ($ (x3X) + (0.5, -0.9) $) .. node [above right, near start] {$1/12$} (x12); \path[-] (x3X) edge node {$1/12$} (x3W); \path (x3W) edge [bend right=20] node {} (x12); diff --git a/re2c/doc/tdfa_v2/part_1_tnfa.tex b/re2c/doc/tdfa_v2/part_1_tnfa.tex index e097523a..e8cf8d37 100644 --- a/re2c/doc/tdfa_v2/part_1_tnfa.tex +++ b/re2c/doc/tdfa_v2/part_1_tnfa.tex @@ -781,7 +781,7 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \begin{figure*} \begin{multicols}{2} \fontsize{8}{10} - \setstretch{0.85} + \setstretch{0.8} %\fontsize{9.5pt}{11.5pt}\selectfont @@ -790,97 +790,100 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \newcommand \retonfa {F} \newcommand \ntag {N} - \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} + \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \Fn {$\underline{\retonfa(r, y)} \smallskip$} { \If {$r = (0, 0, \epsilon)$} { - \Return $(\Sigma, \{y\}, \emptyset, \emptyset, y, y)$ \; + \Return $(\Sigma, \{y\}, \emptyset, \emptyset, y, y)$ } \BlankLine \ElseIf {$r = (0, 0, \alpha) \mid_{\alpha \in \Sigma}$} { - \Return $(\Sigma, \{x,y\}, \emptyset, \{(x, \alpha, \epsilon, y)\}, x, y)$ \; + \Return $(\Sigma, \{x,y\}, \emptyset, \{(x, \alpha, \epsilon, y)\}, x, y)$ } \BlankLine - \ElseIf {$r = (0, 0, r_1 \cdot r_2)$} { - $(\Sigma, Q_1, T_1, \Delta_1, x, y) = \retonfa (r_1, y)$ \; - $(\Sigma, Q_2, T_2, \Delta_2, z, x) = \retonfa (r_2, x)$ \; - \Return $(\Sigma, Q_1 \cup Q_2, T_1 \cup T_2, \Delta_1 \cup \Delta_2, z, y)$ \; + \ElseIf {$r = (0, 0, s \cdot u)$} { + $(\Sigma, Q_s, T_s, \Delta_1, x, y) = \retonfa (s, y)$ \; + $(\Sigma, Q_u, T_u, \Delta_2, z, x) = \retonfa (u, x)$ \; + \Return $(\Sigma, Q_s \cup Q_u, T_s \cup T_u, \Delta_s \cup \Delta_u, z, y)$ } \BlankLine - \ElseIf {$r = (0, 0, r_1 \mid r_2)$} { - $(\Sigma, Q_1, T_1, \Delta_1, x_1, y) = \ntag (r_2, y)$ \; - $(\Sigma, Q_2, T_2, \Delta_2, x_2, x_1) = \retonfa (r_1, x_1)$ \; - $(\Sigma, Q_3, T_3, \Delta_3, x_3, y) = \retonfa (r_2, y)$ \; - $(\Sigma, Q_4, T_4, \Delta_4, x_4, x_3) = \ntag (r_1, x_3)$ \; + \ElseIf {$r = (0, 0, s \mid u)$} { + $(\Sigma, Q_1, T_1, \Delta_1, x_1, y) = \ntag (u, y)$ \; + $(\Sigma, Q_2, T_2, \Delta_2, x_2, x_1) = \retonfa (s, x_1)$ \; + $(\Sigma, Q_3, T_3, \Delta_3, x_3, y) = \retonfa (u, y)$ \; + $(\Sigma, Q_4, T_4, \Delta_4, x_4, x_3) = \ntag (s, x_3)$ \; $Q = Q_1 \cup Q_2 \cup Q_3 \cup Q_4 \cup \{x\}$ \; $T = T_1 \cup T_2 \cup T_3 \cup T_4$ \; $\Delta = \Delta_1 \cup \Delta_2 \cup \Delta_3 \cup \Delta_4 \cup \{(x,1,\epsilon,x_2), (x,2,\epsilon,x_4)\}$ \; - \Return $(\Sigma, Q, T, \Delta, x, y)$ \; + \Return $(\Sigma, Q, T, \Delta, x, y)$ } \BlankLine - \ElseIf {$r = (0, 0, r_1^{n,m}) \mid_{n > 0}$} { - $(\Sigma, Q_1, T_1, \Delta_1, x, y) = \retonfa ((0, 0, r_1^{n-1,m}), y)$ \; - $(\Sigma, Q_2, T_2, \Delta_2, z, x) = \retonfa (r_1, x)$ \; - \Return $(\Sigma, Q_1 \cup Q_2, T_1 \cup T_2, \Delta_1 \cup \Delta_2, z, y)$ \; + \ElseIf {$r = (0, 0, s^{n,m}) \mid_{n > 0}$} { + $(\Sigma, Q_1, T_1, \Delta_1, x, y) = \retonfa ((0, 0, s^{n-1,m}), y)$ \; + $(\Sigma, Q_2, T_2, \Delta_2, z, x) = \retonfa (s, x)$ \; + \Return $(\Sigma, Q_1 \cup Q_2, T_1 \cup T_2, \Delta_1 \cup \Delta_2, z, y)$ } \BlankLine - \ElseIf {$r = (0, 0, r_1^{0,m})$} { - $(\Sigma, Q_1, T_1, \Delta_1, x_1, y) = \retonfa ((0, 0, r_1^{1,m}), y)$ \; - $(\Sigma, Q_2, T_2, \Delta_2, x_2, y) = \ntag (r_1, y)$ \; + \ElseIf {$r = (0, 0, s^{0,m})$} { + $(\Sigma, Q_1, T_1, \Delta_1, x_1, y) = \retonfa ((0, 0, s^{1,m}), y)$ \; + $(\Sigma, Q_2, T_2, \Delta_2, x_2, y) = \ntag (s, y)$ \; $Q = Q_1 \cup Q_2 \cup \{x\}$ \; $\Delta = \Delta_1 \cup \Delta_2 \cup \{(x,1,\epsilon,x_1), (x,2,\epsilon,x_2)\}$ \; - \Return $(\Sigma, Q, T_1 \cup T_2, \Delta, x, y)$ \; + \Return $(\Sigma, Q, T_1 \cup T_2, \Delta, x, y)$ } \BlankLine - \ElseIf {$r = (0, 0, r_1^{1,\infty})$} { - $(\Sigma, Q_1, T_1, \Delta_1, z, x) = \retonfa (r_1, \Xund)$ \; + \ElseIf {$r = (0, 0, s^{1,\infty})$} { + $(\Sigma, Q_1, T_1, \Delta_1, z, x) = \retonfa (s, \Xund)$ \; $Q = Q_1 \cup \{y\}$ \; $\Delta = \Delta_1 \cup \{(x,1,\epsilon,z), (x,2,\epsilon,y)\}$ \; - \Return $(\Sigma, Q, T_1, \Delta, z, y)$ \; + \Return $(\Sigma, Q, T_1, \Delta, z, y)$ } \BlankLine - \ElseIf {$r = (0, 0, r_1^{1,1})$} { - \Return $\retonfa (r_1, y)$ \; + \ElseIf {$r = (0, 0, s^{1,1})$} { + \Return $\retonfa (s, y)$ } \BlankLine - \ElseIf {$r = (0, 0, r_1^{1,m}) \mid_{1 < m < \infty}$} { - $(\Sigma, Q_1, T_1, \Delta_1, x, y) = \retonfa ((0, 0, r_1^{1,m-1}), y)$ \; + \ElseIf {$r = (0, 0, s^{1,m}) \mid_{1 < m < \infty}$} { + $(\Sigma, Q_1, T_1, \Delta_1, x, y) = \retonfa ((0, 0, s^{1,m-1}), y)$ \; $(\Sigma, Q_2, T_2, \Delta_2, w, z) = \retonfa (r_1, \Xund)$ \; $\Delta = \Delta_1 \cup \Delta_2 \cup \{(z,1,\epsilon,y), (z,2,\epsilon,x)\}$ \; - \Return $(\Sigma, Q_1 \cup Q_2, T_1 \cup T_2, \Delta, w, y)$ \; + \Return $(\Sigma, Q_1 \cup Q_2, T_1 \cup T_2, \Delta, w, y)$ } \BlankLine -% \ElseIf {$r = (0, 0, r_1^{1,m}) \mid_{1 < m < \infty}$} { -% $y_m = y$ \; -% \For {$i = \overline{1,m}$} { -% $(\Sigma, Q_i, T_i, \Delta_i, x_i, y_i) = \retonfa (r_1, y_i)$ \; -% } -% $Q = \bigcup\nolimits_{i=1}^m Q_i$ -% $\Delta = \bigcup\nolimits_{i=1}^m \Delta_i \cup \{(y_i,1,\epsilon,y_{i+1}),(y_i,2,\epsilon,x_{i+1})\}_{i=1}^m$ -% \Return $(\Sigma, Q, T, \Delta, x_1, y)$ \; -% } - \BlankLine - \ElseIf {$r = (i, \Xund, r_1) \mid_{i \neq 0}$} { - $(\Sigma, Q_1, T_1, \Delta_1, z, x) = \retonfa (r_1, \Xund)$ \; + \ElseIf {$r = (i, \Xund, s) \mid_{i \neq 0}$} { + $(\Sigma, Q_1, T_1, \Delta_1, z, x) = \retonfa (s, \Xund)$ \; $Q = Q_1 \cup \{w, y\}$ \; $T = T_1 \cup \{2i\!-\!1, 2i\}$ \; $\Delta = \Delta_1 \cup \{(w,1,2i\!-\!1,z), (x,1,2i,y)\}$ \; - \Return $(\Sigma, Q, T, \Delta, w, y)$ \; + \Return $(\Sigma, Q, T, \Delta, w, y)$ } - } \end{algorithm} - \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} + \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \Fn {$\underline{\ntag(r)} \smallskip$} { - \If {$r = (0, 0, \Xund)$} { - \Return $(\Sigma, \{y\}, \emptyset, \emptyset, y, y)$ \; + $T = \{ t_1, \dots, t_n \} = T(r), n \geq 0$ \; + $Q = \{x_0, \dots, x_{2n}\}$ \; + $\Delta = \{(x_{2i},1,1\!-\!2i, x_{2i+1}), (x_i, 1, -\!2i, x_{2i+2})\}_{i=0}^{n-1}$ \; + \Return $(\Sigma, Q, T, \Delta, x_0, x_{2n})$ \; + } + \end{algorithm} + + + \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} + \Fn {$\underline{T((i, \Xund, r))} \smallskip$} { + \lIf {$i = 0$} { + \Return $\emptyset$ } - \BlankLine - \ElseIf {$r = (i, \Xund, \Xund) \mid_{i \neq 0}$} { - \Return $(\Sigma, \{x,y\}, \{1\!-\!2i\}, \{(x, 1, 1\!-\!2i, y)\}, x, y)$ \; + \lElseIf {$r = s \mid u \vee r = s \cdot u$} { + \Return $\{i\} \cup T(s) \cup T(u)$ + } + \lElseIf {$r = s^{n,m}$} { + \Return $\{i\} \cup T(s)$ + } + \lElse { + \Return $\{i\}$ } - } \end{algorithm} @@ -892,17 +895,14 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \end{multicols} -%\vspace{-2em} -%\includegraphics[width=\linewidth]{img/tnfa_example.pdf} \vspace{-2em} -\begin{center} \caption{TNFA construction.} -\end{center} \end{figure*} \begin{figure}\label{fig_tnfa_example} \includegraphics[width=\linewidth]{img/tnfa_example.pdf} +\vspace{-2em} \caption{ Example TNFA for RE $(a|\epsilon)^{0,3}((a^{0,\infty})|(\epsilon))$. } -- 2.49.0