# HG changeset patch # User Ryoma SHINYA # Date 1281705103 -32400 # Node ID 3bf6db862bc7ec1465e6e22bdd25237699517ce7 # Parent e79cdc772194dc561f561a1ec9490a1ebc6f86e1 ver:1 diff -r e79cdc772194 -r 3bf6db862bc7 fig1.eps --- a/fig1.eps Thu Aug 12 04:55:49 2010 +0900 +++ b/fig1.eps Fri Aug 13 22:11:43 2010 +0900 @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.26.3 (20100126.1600) %%Title: G %%Pages: 1 -%%BoundingBox: 36 36 284 125 +%%BoundingBox: 36 36 380 125 %%EndComments save %%BeginProlog @@ -178,17 +178,17 @@ %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 284 125 +%%PageBoundingBox: 36 36 380 125 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 248 89 boxprim clip newpath +36 36 344 89 boxprim clip newpath 1 1 set_scale 0 rotate 40 41 translate % regex gsave 0 0 0 nodecolor 14 /Times-Roman set_font -21.5 12.9 moveto 11 (A) alignedtext +16.5 12.9 moveto 21 (AB) alignedtext grestore % q0 gsave @@ -205,42 +205,77 @@ % q1 gsave 0 0 1 nodecolor -215 56 20.8 20.8 ellipse_path fill +211 56 20.8 20.8 ellipse_path fill 1 setlinewidth filled 0 0 0 nodecolor -215 56 20.8 20.8 ellipse_path stroke -1 setlinewidth -filled -0 0 0 nodecolor -215 56 24.8 24.8 ellipse_path stroke +211 56 20.8 20.8 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -207 50.9 moveto 16 (q1) alignedtext +203 50.9 moveto 16 (q1) alignedtext grestore % q0->q1 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 134.13 56 moveto -147.31 56 164.6 56 179.81 56 curveto +newpath 134.26 56 moveto +147.49 56 164.74 56 179.53 56 curveto stroke 0 0 0 edgecolor -newpath 179.93 59.5 moveto -189.93 56 lineto -179.93 52.5 lineto +newpath 179.78 59.5 moveto +189.78 56 lineto +179.78 52.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 179.93 59.5 moveto -189.93 56 lineto -179.93 52.5 lineto +newpath 179.78 59.5 moveto +189.78 56 lineto +179.78 52.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font 152.5 58.4 moveto 19 ('A') alignedtext grestore +% q2 +gsave +0 0 1 nodecolor +311 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +311 56 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +311 56 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +303 50.9 moveto 16 (q2) alignedtext +grestore +% q1->q2 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 232.21 56 moveto +244.85 56 261.21 56 275.75 56 curveto +stroke +0 0 0 edgecolor +newpath 275.94 59.5 moveto +285.94 56 lineto +275.94 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 275.94 59.5 moveto +285.94 56 lineto +275.94 52.5 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +250 58.4 moveto 18 ('B') alignedtext +grestore % start gsave 0 0 0 nodecolor diff -r e79cdc772194 -r 3bf6db862bc7 fig2.eps --- a/fig2.eps Thu Aug 12 04:55:49 2010 +0900 +++ b/fig2.eps Fri Aug 13 22:11:43 2010 +0900 @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.26.3 (20100126.1600) %%Title: G %%Pages: 1 -%%BoundingBox: 36 36 284 125 +%%BoundingBox: 36 36 364 160 %%EndComments save %%BeginProlog @@ -178,11 +178,11 @@ %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 284 125 +%%PageBoundingBox: 36 36 364 160 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 248 89 boxprim clip newpath +36 36 328 124 boxprim clip newpath 1 1 set_scale 0 rotate 40 41 translate % regex gsave @@ -193,6 +193,92 @@ % q0 gsave 0 0 1 nodecolor +193 95 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +193 95 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +185 89.9 moveto 16 (q0) alignedtext +grestore +% q3 +gsave +0 0 1 nodecolor +295 67 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +295 67 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +295 67 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +287 61.9 moveto 16 (q3) alignedtext +grestore +% q0->q3 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 213.64 89.33 moveto +227.2 85.61 245.27 80.65 260.93 76.35 curveto +stroke +0 0 0 edgecolor +newpath 262.09 79.66 moveto +270.8 73.64 lineto +260.23 72.91 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 262.09 79.66 moveto +270.8 73.64 lineto +260.23 72.91 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +232.5 85.4 moveto 19 ('A') alignedtext +grestore +% q1 +gsave +0 0 1 nodecolor +193 35 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +193 35 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +185 29.9 moveto 16 (q1) alignedtext +grestore +% q1->q3 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 213.15 41.32 moveto +226.77 45.6 245.1 51.34 260.95 56.32 curveto +stroke +0 0 0 edgecolor +newpath 260.35 59.8 moveto +270.94 59.45 lineto +262.45 53.12 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 260.35 59.8 moveto +270.94 59.45 lineto +262.45 53.12 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +233 54.4 moveto 18 ('B') alignedtext +grestore +% q2 +gsave +0 0 1 nodecolor 113 56 20.8 20.8 ellipse_path fill 1 setlinewidth filled @@ -200,70 +286,47 @@ 113 56 20.8 20.8 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -105 50.9 moveto 16 (q0) alignedtext +105 50.9 moveto 16 (q2) alignedtext grestore -% q1 -gsave -0 0 1 nodecolor -215 56 20.8 20.8 ellipse_path fill -1 setlinewidth -filled -0 0 0 nodecolor -215 56 20.8 20.8 ellipse_path stroke -1 setlinewidth -filled -0 0 0 nodecolor -215 56 24.8 24.8 ellipse_path stroke -0 0 0 nodecolor -14 /Times-Roman set_font -207 50.9 moveto 16 (q1) alignedtext -grestore -% q0->q1 +% q2->q0 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 134.13 56 moveto -147.31 56 164.6 56 179.81 56 curveto +newpath 131.96 65.24 moveto +141.75 70.02 153.89 75.94 164.77 81.24 curveto stroke 0 0 0 edgecolor -newpath 179.93 59.5 moveto -189.93 56 lineto -179.93 52.5 lineto +newpath 163.38 84.45 moveto +173.9 85.69 lineto +166.44 78.16 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 179.93 59.5 moveto -189.93 56 lineto -179.93 52.5 lineto +newpath 163.38 84.45 moveto +173.9 85.69 lineto +166.44 78.16 lineto closepath stroke -0 0 0 edgecolor -14 /Times-Roman set_font -152.5 58.4 moveto 19 ('A') alignedtext grestore -% q0->q1 +% q2->q1 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 131.01 45.12 moveto -137.41 41.83 144.81 38.66 152 37 curveto -162.35 34.61 173.5 36.47 183.49 39.8 curveto +newpath 133.6 50.59 moveto +142.47 48.26 153.01 45.5 162.73 42.94 curveto stroke 0 0 0 edgecolor -newpath 182.45 43.14 moveto -193.03 43.52 lineto -184.99 36.62 lineto +newpath 163.68 46.31 moveto +172.47 40.39 lineto +161.91 39.54 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 182.45 43.14 moveto -193.03 43.52 lineto -184.99 36.62 lineto +newpath 163.68 46.31 moveto +172.47 40.39 lineto +161.91 39.54 lineto closepath stroke -0 0 0 edgecolor -14 /Times-Roman set_font -153 39.4 moveto 18 ('B') alignedtext grestore % start gsave @@ -274,7 +337,7 @@ 0 0 0 nodecolor 27 56 1.8 1.8 ellipse_path stroke grestore -% start->q0 +% start->q2 gsave 1 setlinewidth 0 0 0 edgecolor diff -r e79cdc772194 -r 3bf6db862bc7 fig3.eps --- a/fig3.eps Thu Aug 12 04:55:49 2010 +0900 +++ b/fig3.eps Fri Aug 13 22:11:43 2010 +0900 @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.26.3 (20100126.1600) %%Title: G %%Pages: 1 -%%BoundingBox: 36 36 186 158 +%%BoundingBox: 36 36 243 194 %%EndComments save %%BeginProlog @@ -178,85 +178,148 @@ %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 186 158 +%%PageBoundingBox: 36 36 243 194 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 150 122 boxprim clip newpath +36 36 207 158 boxprim clip newpath 1 1 set_scale 0 rotate 40 41 translate % regex gsave 0 0 0 nodecolor 14 /Times-Roman set_font -17.5 12.9 moveto 19 (A*) alignedtext +161.5 52.9 moveto 19 (A*) alignedtext grestore % q0 gsave 0 0 1 nodecolor -117 56 20.8 20.8 ellipse_path fill +134 127.71 20.8 20.8 ellipse_path fill 1 setlinewidth filled 0 0 0 nodecolor -117 56 20.8 20.8 ellipse_path stroke +134 127.71 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +126 122.61 moveto 16 (q0) alignedtext +grestore +% q1 +gsave +0 0 1 nodecolor +98 65.35 20.8 20.8 ellipse_path fill 1 setlinewidth filled 0 0 0 nodecolor -117 56 24.8 24.8 ellipse_path stroke +98 65.35 20.8 20.8 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -109 50.9 moveto 16 (q0) alignedtext +90 60.25 moveto 16 (q1) alignedtext grestore -% q0->q0 +% q0->q1 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 108.85 79.88 moveto -108.18 90.18 110.9 99 117 99 curveto -120.91 99 123.43 95.38 124.56 90.07 curveto +newpath 129.11 106.93 moveto +126.28 100.95 122.7 94.41 118.96 88.31 curveto stroke 0 0 0 edgecolor -newpath 128.07 90.06 moveto -125.15 79.88 lineto -121.08 89.66 lineto +newpath 121.82 86.29 moveto +113.44 79.81 lineto +115.95 90.11 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 121.82 86.29 moveto +113.44 79.81 lineto +115.95 90.11 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +125.54 86.52 moveto 19 ('A') alignedtext +grestore +% q1->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 102.89 86.13 moveto +105.72 92.11 109.3 98.65 113.04 104.75 curveto +stroke +0 0 0 edgecolor +newpath 110.18 106.77 moveto +118.56 113.25 lineto +116.05 102.96 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 128.07 90.06 moveto -125.15 79.88 lineto -121.08 89.66 lineto +newpath 110.18 106.77 moveto +118.56 113.25 lineto +116.05 102.96 lineto closepath stroke -0 0 0 edgecolor +grestore +% q2 +gsave +0 0 1 nodecolor +26 65.35 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +26 65.35 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +26 65.35 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor 14 /Times-Roman set_font -107.5 101.4 moveto 19 ('A') alignedtext +18 60.25 moveto 16 (q2) alignedtext +grestore +% q1->q2 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 76.79 65.35 moveto +71.88 65.35 66.54 65.35 61.21 65.35 curveto +stroke +0 0 0 edgecolor +newpath 61.13 61.85 moveto +51.13 65.35 lineto +61.13 68.85 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 61.13 61.85 moveto +51.13 65.35 lineto +61.13 68.85 lineto +closepath stroke grestore % start gsave 0 0 0 nodecolor -27 56 1.8 1.8 ellipse_path fill +134 3 1.8 1.8 ellipse_path fill 1 setlinewidth filled 0 0 0 nodecolor -27 56 1.8 1.8 ellipse_path stroke +134 3 1.8 1.8 ellipse_path stroke grestore -% start->q0 +% start->q1 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 28.88 56 moveto -35.73 56 60.11 56 81.49 56 curveto +newpath 132.96 4.8 moveto +130.05 9.84 121.5 24.66 113.58 38.37 curveto stroke 0 0 0 edgecolor -newpath 81.65 59.5 moveto -91.65 56 lineto -81.65 52.5 lineto +newpath 110.51 36.69 moveto +108.54 47.1 lineto +116.57 40.19 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 81.65 59.5 moveto -91.65 56 lineto -81.65 52.5 lineto +newpath 110.51 36.69 moveto +108.54 47.1 lineto +116.57 40.19 lineto closepath stroke grestore endpage diff -r e79cdc772194 -r 3bf6db862bc7 fig4.eps --- a/fig4.eps Thu Aug 12 04:55:49 2010 +0900 +++ b/fig4.eps Fri Aug 13 22:11:43 2010 +0900 @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.26.3 (20100126.1600) %%Title: G %%Pages: 1 -%%BoundingBox: 36 36 294 187 +%%BoundingBox: 36 36 392 201 %%EndComments save %%BeginProlog @@ -178,144 +178,271 @@ %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 294 187 +%%PageBoundingBox: 36 36 392 201 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 258 151 boxprim clip newpath +36 36 356 165 boxprim clip newpath 1 1 set_scale 0 rotate 40 41 translate % regex gsave 0 0 0 nodecolor 14 /Times-Roman set_font -8 12.9 moveto 50 (\(A|B\)*C) alignedtext +8 29.9 moveto 50 (\(A|B\)*C) alignedtext grestore % q0 gsave 0 0 1 nodecolor -125 56 20.8 20.8 ellipse_path fill +33 125 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +33 125 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +25 119.9 moveto 16 (q0) alignedtext +grestore +% q3 +gsave +0 0 1 nodecolor +143 82 20.8 20.8 ellipse_path fill 1 setlinewidth filled 0 0 0 nodecolor -125 56 20.8 20.8 ellipse_path stroke +143 82 20.8 20.8 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -117 50.9 moveto 16 (q0) alignedtext +135 76.9 moveto 16 (q3) alignedtext grestore -% q0->q0 +% q0->q3 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 121.32 76.86 moveto -120.92 86.54 122.15 95 125 95 curveto -126.74 95 127.87 91.86 128.4 87.22 curveto +newpath 52.67 117.31 moveto +69.61 110.69 94.32 101.03 113.61 93.49 curveto stroke 0 0 0 edgecolor -newpath 131.91 86.95 moveto -128.68 76.86 lineto -124.91 86.77 lineto +newpath 115.09 96.67 moveto +123.13 89.77 lineto +112.55 90.15 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 131.91 86.95 moveto -128.68 76.86 lineto -124.91 86.77 lineto +newpath 115.09 96.67 moveto +123.13 89.77 lineto +112.55 90.15 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -115.5 97.4 moveto 19 ('A') alignedtext +84.5 106.4 moveto 19 ('A') alignedtext grestore -% q0->q0 +% q1 +gsave +0 0 1 nodecolor +323 105 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +323 105 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +315 99.9 moveto 16 (q1) alignedtext +grestore +% q1->q3 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 111.79 72.34 moveto -102.41 91.18 106.81 113 125 113 curveto -140.2 113 145.78 97.75 141.72 81.74 curveto +newpath 302.28 100.82 moveto +286.39 97.74 263.88 93.64 244 91 curveto +220.78 87.91 194.4 85.6 174.43 84.1 curveto stroke 0 0 0 edgecolor -newpath 144.98 80.49 moveto -138.21 72.34 lineto -138.43 82.93 lineto +newpath 174.57 80.6 moveto +164.34 83.36 lineto +174.06 87.58 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 174.57 80.6 moveto +164.34 83.36 lineto +174.06 87.58 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +214 93.4 moveto 18 ('B') alignedtext +grestore +% q2 +gsave +0 0 1 nodecolor +223 136 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +223 136 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +215 130.9 moveto 16 (q2) alignedtext +grestore +% q2->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 201.85 134.78 moveto +168.4 132.84 103.14 129.06 64.27 126.81 curveto +stroke +0 0 0 edgecolor +newpath 64.24 123.3 moveto +54.06 126.22 lineto +63.84 130.29 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 144.98 80.49 moveto -138.21 72.34 lineto -138.43 82.93 lineto +newpath 64.24 123.3 moveto +54.06 126.22 lineto +63.84 130.29 lineto closepath stroke +grestore +% q2->q1 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 243.24 129.73 moveto +257.47 125.31 276.76 119.33 292.8 114.36 curveto +stroke +0 0 0 edgecolor +newpath 294.28 117.57 moveto +302.79 111.26 lineto +292.21 110.88 lineto +closepath fill +1 setlinewidth +solid 0 0 0 edgecolor -14 /Times-Roman set_font -116 115.4 moveto 18 ('B') alignedtext +newpath 294.28 117.57 moveto +302.79 111.26 lineto +292.21 110.88 lineto +closepath stroke grestore -% q1 +% q3->q2 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 160.75 93.98 moveto +171.39 101.16 185.11 110.42 196.96 118.42 curveto +stroke +0 0 0 edgecolor +newpath 195.32 121.54 moveto +205.57 124.23 lineto +199.24 115.74 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 195.32 121.54 moveto +205.57 124.23 lineto +199.24 115.74 lineto +closepath stroke +grestore +% q4 gsave 0 0 1 nodecolor -225 56 20.8 20.8 ellipse_path fill +223 25 20.8 20.8 ellipse_path fill 1 setlinewidth filled 0 0 0 nodecolor -225 56 20.8 20.8 ellipse_path stroke -1 setlinewidth -filled -0 0 0 nodecolor -225 56 24.8 24.8 ellipse_path stroke +223 25 20.8 20.8 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -217 50.9 moveto 16 (q1) alignedtext +215 19.9 moveto 16 (q4) alignedtext grestore -% q0->q1 +% q3->q4 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 146.21 56 moveto -158.85 56 175.21 56 189.75 56 curveto +newpath 160.36 69.63 moveto +171.16 61.94 185.24 51.91 197.31 43.3 curveto stroke 0 0 0 edgecolor -newpath 189.94 59.5 moveto -199.94 56 lineto -189.94 52.5 lineto +newpath 199.56 46 moveto +205.68 37.34 lineto +195.5 40.3 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 189.94 59.5 moveto -199.94 56 lineto -189.94 52.5 lineto +newpath 199.56 46 moveto +205.68 37.34 lineto +195.5 40.3 lineto +closepath stroke +grestore +% q5 +gsave +0 0 1 nodecolor +323 25 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +323 25 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +323 25 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +315 19.9 moveto 16 (q5) alignedtext +grestore +% q4->q5 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 244.21 25 moveto +256.85 25 273.21 25 287.75 25 curveto +stroke +0 0 0 edgecolor +newpath 287.94 28.5 moveto +297.94 25 lineto +287.94 21.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 287.94 28.5 moveto +297.94 25 lineto +287.94 21.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -164 58.4 moveto 18 ('C') alignedtext +262 27.4 moveto 18 ('C') alignedtext grestore % start gsave 0 0 0 nodecolor -33 56 1.8 1.8 ellipse_path fill +33 73 1.8 1.8 ellipse_path fill 1 setlinewidth filled 0 0 0 nodecolor -33 56 1.8 1.8 ellipse_path stroke +33 73 1.8 1.8 ellipse_path stroke grestore -% start->q0 +% start->q3 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 34.92 56 moveto -42.48 56 70.91 56 93.83 56 curveto +newpath 34.91 73.16 moveto +43.95 73.9 83.25 77.11 111.86 79.45 curveto stroke 0 0 0 edgecolor -newpath 93.88 59.5 moveto -103.88 56 lineto -93.88 52.5 lineto +newpath 111.59 82.94 moveto +121.84 80.27 lineto +112.16 75.96 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 93.88 59.5 moveto -103.88 56 lineto -93.88 52.5 lineto +newpath 111.59 82.94 moveto +121.84 80.27 lineto +112.16 75.96 lineto closepath stroke grestore endpage diff -r e79cdc772194 -r 3bf6db862bc7 paper.pdf Binary file paper.pdf has changed diff -r e79cdc772194 -r 3bf6db862bc7 paper.tex --- a/paper.tex Thu Aug 12 04:55:49 2010 +0900 +++ b/paper.tex Fri Aug 13 22:11:43 2010 +0900 @@ -84,12 +84,18 @@ ば Java の HotSpot や Python の PyPy など, 仮想マシンを持つ言語処理系の 最適化技術として利用されている. -実行時コンパイルが可能な対象として, 正規表現評価器に着目し,コンパイラ基 -盤であるLLVM, GCC をバックエンドに用いた実行時コンパイルを行う評価器を -Pythonによって実装した. +実行時コンパイルが可能な対象として, 正規表現評価器に着目した. +現在,正規表現の評価器は, プログラミング言語の組み込み機能やライブラリ等, +さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\cite{R2}. +仮想マシンを採用いた実装でも, 正規表現を内部表現に変換する処理を行ってお +り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装した評価器の +``実行時コンパイル''とは, 正規表現を内部形式に変換することではなく, 正規 +表現 から実行バイナリを生成することを指す(\ref{subsection:compile}節). 本研究では, 実行バイナリの生 +成にはコンパイラ基盤であるLLVM, GCC を用いており,評価器全体の実装として +はPythonで実装した. 本論文では, まず正規表現のコンパイル方法について説明し, 実装した評価器の -性能調査のために, 正規表現を用いてテキストマッチ検査を行う grep と同等の +性能調査のために, 正規表現を用いてテキストマッチ処理を行う grep と同等の 機能を実装し, GNU grep との比較を行う. \section{正規表現} @@ -97,51 +103,119 @@ 正規表現は与えられた文字列を受理するかどうかを判定できるパターンマッチン グの機構であり, sed, grep, awk を始めとするテキスト処理ツールに広く利用 されている. 正規表現には定められた文法によって記述され, 例えば,正規表現 -``a*b''は''a''の0回以上の繰り返し ``b'' で終わる文字列(``b'', ``ab'', -``'aaaab')を受理し, ``a(b|c)'' は ``a''で始まり,直後が ``b'' または +``a*b''は''a''の0回以上の繰り返し直後, ``b'' で終わる文字列(``b'', ``ab'', +``'aaaab')を受理し, ``a(b\textbar c)'' は ``a''で始まり,直後が ``b'' または ``c''で終わる文字列(``ab'', ``ac'') を受理する. +\subsection{正規表現の演算}\label{subsection:regex} + +本論文では, 以下に定義された演算をサポートする表現を正規表現として扱う. +\begin{enumerate} +\item {連接} 二つの言語LとMの連接(LM)は, Lに族する列を一つとり, そのあとにMに族する列を連 +接することによってできる列全体から成る集合である. +\item {集合和} 二つの言語LとM集合和(L\textbar M)は, LまたはM(もしくはその両方)に属する列全体からなる +集合である. +\item {閉包} 言語Lの閉包(L*)とは, Lの中から有限個の列を重複を許して取り出し, + それらを連接してできる列全体の集合である. +\end{enumerate} + +正規表現は,この3つの演算について閉じておリ,この3つの演算によって定義され +る表現は, 数学的には正則表現と定義されている. +本論文では,特に区別のない限り,正則表現と正規表現を同じものとして扱う. + \subsection{grep} +正規表現は, テキストのパターンをシンプルに記述できるという利点から, テキ +ストファイルから, 任意のパターンにマッチするテキストを検索するなどの用途 +に使用される. -\section{正規表現の実行時コンパイル} +GNU grep は, それを実現するソフトウェアの一つであり, 引数として与えられ +たファイルから, 与えられた正規表現にマッチするテキストを含む行を出力する +機能を持っている. + +``与えられた正規表現にマッチするテキストを含む''というのは, 行の先頭から +末尾まで正規表現によるマッチングを行い, 正規表現が受理状態になった時点で +``含む'' という解釈を行う.つまり, 正規表現 ''(a\textbar s)t'' は, ''at''または'' +st``を受理する正規表現であり, テキスト行''math.``の2~3文字目の''at''に一致す +るので grep は ``math.'' を出力する. また正規表現''a*''は, ``a''の0回以上の繰 +り返しを受理する正規表現であり, 空文字も受理するので, grep は全ての行を +出力することになる. + +\section{正規表現評価器の実装} +正規表現は等価なNFAに, またNFAは等価なDFAに変換することが可能である\cite{U}. 以 +下にその変換手方を説明する. + \subsection{正規表現からNFAへの変換} -\subsection{NFAからDFAへの変換} -は +NFA は, 入力に対して複数の遷移先持つ状態の集合である. + +正規表現が, 等価なNFAに変換できるということを,\ref{subsection:regex}で定義 +した3つの演算について対応するNFAに変換できることから示す. -\begin{figure}[!tb] +\begin{enumerate} +\item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFAとなる. +\item {集合和} 図\ref{figure:union}は正規表現 ``A|B''に対応するNFAとなる. +\item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFAとなる. +\end{enumerate} + +\begin{figure}[tH] \begin{center} \scalebox{0.80}{\includegraphics{fig1.eps}} \end{center} +\caption{``A''と``B''の連接} +\label{figure:concat} \end{figure} \begin{figure}[tb] \begin{center} \scalebox{0.80}{\includegraphics{fig2.eps}} \end{center} +\caption{``A''と``B''の集合和} +\label{figure:union} \end{figure} \begin{figure}[tb] \begin{center} \scalebox{0.80}{\includegraphics{fig3.eps}} \end{center} +\caption{``A''の閉包} +\label{figure:star} \end{figure} -\subsection{DFAからContinuous base Cへの変換} +図\ref{figure:union}, \ref{figure:star}において, ラベルのない矢印は無条件 +の遷移を現しており,$\varepsilon$-動作と呼ばれる. また, 二重丸で囲まれた +状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で,受理状態を保 +持している場合に限り, その文字列を受理したことになる. + +現在実装されている正規表現評価器の多くは, 正規表現を内部的にNFAに変換し +て評価を行っている\cite{R1}. NFAによる実装は, 後述する後方参照や最長一致 +に対応しやすいが, 複数の状態を保持する必要があるため + +\subsection{NFAからDFAへの変換} +\subsection{DFAから実行バイナリの生成}\label{subsection:compile} +DFAからの実行バイナリ生成には, 3種類の実装を行った. +\begin{enumerate} +\item ({\bf DFA -> Continuous based C -> gccによるコンパイル}) +\item ({\bf DFA -> C -> gccによるコンパイル }) +\item ({\bf DFA -> LLVM 中間表現 -> LLVMによるコンパイル}) +\end{enumerate} % \section{評価} - ... \begin{adjustvboxheight} % needed only when Appendix follows \begin{thebibliography}{99} -\bibitem{K} Ken Thompson : Regular Expression Search Algorithm, 1968 +\bibitem{U} Hopcroft, J, E. Motowani, R. D, Ullman. : オートマトン言 + 語理論計算論I (第二版), pp.~39--90. -\bibitem{R1} Russ Cox : Regular Expression Matching Can Be Simple And +\bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968 + +\bibitem{R1} Cox, R : Regular Expression Matching Can Be Simple And Fast, 2007 -\bibitem{R2} Russ Cox : Regular Expression Matching: the Virtual Machine + +\bibitem{R2} Cox, R : Regular Expression Matching: the Virtual Machine Approach, 2009 -\bibitem{R3} Russ Cox : Regular Expression Matching in the Wild, 2010 + +\bibitem{R3} Cox, R : Regular Expression Matching in the Wild, 2010 \bibitem{H} 長谷川 勇 : 国際正規表現ライブラリの開発