Thuật toán mới xác định độ trễ giải mã của ngôn ngữ chính quy

T¤p ch½ Tin håc v  i·u khiºn håc, T.28, S.2 (2012), 141-152<br /> <br /> THUŠT TON MÎI XC ÀNH Ë TR™ GIƒI M‚<br /> CÕA NGÆN NGÚ CHNH QUY<br /> 0xq …‰˜„ „rxq1 D xq…‰™x 0œxr r…x2 D €rex „‚…xq r…‰3<br /> 1 Tr÷íng<br /> <br /> ¤i håc S÷ ph¤m Kÿ thuªt Nam ành<br /> <br /> 2 Tr÷íng<br /> <br /> ¤i håc S÷ ph¤m Kÿ thuªt H÷ng Y¶n<br /> <br /> 3 Tr÷íng<br /> <br /> ¤i håc B¡ch khoa H  Nëi<br /> <br /> Tóm t t. f i ˜¡o 1· xu§t mët gi£i thuªt mîi x¡™ 1ành 1ë tr¹ gi£i m¢ ™õ— ngæn ngú ™h½nh quy 1÷ñ™<br /> 1o¡n nhªn ˜ði ætæm—t húu h¤n AF qi£i thuªt ™â 1ë phù™ t¤p thíi gi—n l  O(n3 )D ð 1â n l  sè ™ung<br /> v  tr¤ng th¡i ™õ— AF<br /> Abstract. sn this p—perD we propose — new —lgorithm determining de™iphering del—y of regul—r<br /> l—ngu—geD whi™h re™ognizes ˜y — finite —utom—ton AF „he —lgorithm h—s time ™omplexity O(n3 )D<br /> where n is the num˜er of st—tes —nd edges of AF<br /> <br /> 1. GIÎI THI›U<br /> „rong ™¡™ ph²p gi£i m¢ thæng th÷íngD khi x¥u ™¦n gi£i m¢ 1÷ñ™ 1å™ tø tr¡i qu— ph£iD thíi<br /> 1iºm ph¡t hi»n th§y mët tø m¢ trong x¥u v  thíi 1iºm t§t ™£ ™¡™ tø m¢ trong x¥u 1÷ñ™ x¡™<br /> 1ành mët ™¡™h ™h­™ ™h­n l  kh¡™ nh—uF uho£ng thíi gi—n tr¹ n y 1÷ñ™ h¼nh thù™ h◠˜¬ng<br /> kh¡i ni»m 1ë tr¹ gi£i m¢D kh¡i ni»m n y xu§t hi»n r§t sîm trong lþ thuy¸t m¢D nh÷ trong ™¡™<br /> ™æng tr¼nh ™õ— qil˜ert —nd woore @IWSWA @xem ‘W“AD ™õ— vevenshtein @IWTRA @xem ‘IH“AF †îi<br /> kh¡i ni»m 1ë tr¹ gi£i m¢ th¼ lîp m¢ prefix l  lîp m¢ ™â 1ë tr¹ gi£i m¢ ˜¬ng HD tø 1â 1ë tr¹<br /> gi£i m¢ 1÷ñ™ sû döng trong lþ thuy¸t m¢ nh÷ l  mët ti¶u ™hu©n qu—n trång 1º ph¥n lo¤i m¢<br /> v  l  mët th—m sè ph£n ¡nh 1ë khâ trong qu¡ tr¼nh gi£i m¢F 0èi vîi ™¡™ ùng döngD vi»™ x¡™<br /> 1ành ™h½nh x¡™ 1ë tr¹ gi£i m¢ ™õ— mët ngæn ngúD ™ho ph²p ™¡™ ™h÷ìng tr¼nh mªt m¢ t«ng<br /> hi»u qu£ thíi gi—n v  lo¤i ˜ä 1÷ñ™ th—o t¡™ qu—y lui trong qu¡ tr¼nh gi£i m¢F ho v—i trá qu—n<br /> trång ™õ— 1ë tr¹ gi£i m¢D nhi·u t¡™ gi£ 1¢ qu—n t¥m nghi¶n ™ùuD mët lo¤t ™¡™ ™æng tr¼nh nh÷<br /> ™õ— w—rkov @IWTPA @xem ‘IP“AD ƒ™h¤tzen˜erger @IWTTA @xem ‘II“AD ghoffrut @IWUWA @xem ‘IQ“AD<br /> u<br /> vF ƒt—iger @IWVTA @xem ‘S“AD tF hevolder @IWWRA @xem ‘Q“AD ƒt—vros uonst—ntinidis @PHHPA @xem<br /> ‘V“AD €F„F ruyE†F„F x—m @PHHPA @xem ‘IR“AD hF vF †—n ! sF vitovsky @PHHQA @xem ‘IU“AD xFhF<br /> r—n E hFF „h—ng E rFxF †inh @PHIHA @xem ‘IT“AD FFF tªp trung nghi¶n ™ùu t½nh ™h§t ™õ— 1ë<br /> tr¹ gi£i m¢F<br /> gho 1¸n n—yD vi»™ t½nh to¡n ™h½nh x¡™ 1ë tr¹ gi£i m¢ 1÷ñ™ nhi·u t¡™ gi£ qu—n t¥mD ph÷ìng<br /> ph¡p t½nh to¡n ™hõ y¸u dü— tr¶n ™¡™h ti¸p ™ªn tê hñp v  þ t÷ðng tø thõ tö™ kiºm tr— t½nh ™h§t<br /> m¢ ™õ— mët ngæn ngú @thõ tö™ ƒ—rdin—sE€—ttersonA @xem ‘IRD IT“AD h—y x¡™ 1ành mët m¡y ˜i¸n<br /> 1êi ™â l  h m h—y khæng @xem ‘V“AF qi£i thuªt tèt nh§t 1÷ñ™ ˜i¸t ™ho tîi n—y l  gi£i thuªt ™õ—<br /> ƒt—vros uonst—ntinidis @xem ‘V“AD gi£i thuªt n y ™â 1ë phù™ t¤p thíi gi—n trong tr÷íng hñp<br /> <br /> 142<br /> <br /> NG QUY˜T THNG, NGUY™N œNH H…N, PHAN TRUNG HUY<br /> <br /> x§u nh§t l  O(n4 log n)F 0º ™ho gånD khi 1· ™ªp 1¸n 1ë phù™ t¤p thíi gi—n th¼ luæn 1÷ñ™ hiºu<br /> l  1ë phù™ t¤p thíi gi—n trong tr÷íng hñp x§u nh§tF<br /> f i ˜¡o 1· xu§t gi£i thuªt mîi x¡™ 1ành 1ë tr¹ gi£i m¢ ™õ— ngæn ngú ™h½nh quy 1÷ñ™ 1o¡n<br /> nhªn ˜ði ætæm—t húu h¤n AD sû döng kÿ thuªt s—o ™h²p 1ç thàD gh²p v  t½™h ætæm—tD tø kÿ<br /> thuªt n y ™ho ph²p x¥y düng gi£i thuªt ™â 1ë phù™ t¤p thíi gi—n O(n3 )F<br /> wö™ P s³ tr¼nh ˜ y mët sè kh¡i ni»m ngæn ngúD m¢D 1ë tr¹ gi£i m¢D ætæm—t v  1ç thà 1º<br /> phö™ vö ™ho ™¡™ mö™ ti¸p theoF wö™ Q tr¼nh ˜ y ™¡™ gi£i thuªt mð rëng ætæm—tF wö™ R 1·<br /> xu§t gi£i thuªt mîi x¡™ 1ành 1ë tr¹ gi£i m¢ v  ™uèi ™òng l  ph¦n k¸t luªn ™õ— ˜ i ˜¡oF<br /> <br /> 2. MËT SÈ KHI NI›M<br /> „r÷î™ h¸tD t— nh­™ l¤i mët sè kh¡i ni»m v  kþ hi»u 1÷ñ™ sû döng trong ˜ i ˜¡o @™hi ti¸t<br /> xem trong ‘PD R“AF gho ˜£ng ™hú ™¡i húu h¤n ΣD kþ hi»u Σ∗ l  tªp t§t ™£ ™¡™ tø húu h¤n tr¶n<br /> ΣF „ø réng kþ hi»u l  ε v  Σ+ = Σ∗ − {ε}F „ªp ™on ™õ— Σ∗ gåi l  ngæn ngúF gho L ⊆ Σ∗ l <br /> ngæn ngú tr¶n ΣF „— kþ hi»uX<br /> L∗ = L0 ∪ L1 ∪ · · · D ð 1â L0 = {ε}D L1 = LD L2 = L1 L, . . . , Ln = Ln−1 LD<br /> L+ = L1 ∪ L2 ∪ . . .D t— ™â L∗ = L+ ∪ {ε}F<br /> <br /> ành ngh¾a 2.1. Cho b£ng chú c¡i Σ, tªp L ⊆ Σ∗ ÷ñc gåi l  m¢ n¸u vîi måi m, n ≥ 1 v <br /> <br /> vîi måi x1, . . . , xn, y1, . . . , ym ∈ L, n¸u câ x1 · · · xn = y1 · · · ym th¼ suy ra m = n v  xi = yi<br /> vîi i = 1, . . . , n.<br /> <br /> xâi ™¡™h kh¡™D tªp L l  m¢ n¸u måi x¥u trong L+ ™h¿ ™â mët ph¥n t½™h duy nh§t th nh<br /> ™¡™ x¥u trong LF ho ε.ε = ε n¶n måi tªp m¢ 1·u khæng ™hù— x¥u réngF<br /> <br /> ành ngh¾a 2.2. Cho L ⊆ Σ+, L ÷ñc gåi l  câ ë tr¹ gi£i m¢ húu h¤n n¸u tçn t¤i mët sè<br /> nguy¶n d ≥ 0 sao cho:<br /> <br /> ∀x, x ∈ L, ∀y ∈ Ld , ∀u ∈ Σ∗ , xyu ∈ x L∗ ⇒ x = x .<br /> <br /> (2.1)<br /> <br /> h¹ th§y r¬ng n¸u h» thù™ @PFIA thä— m¢n vîi d húu h¤n n o 1â th¼ n⠙ông 1óng vîi måi<br /> d ≥ dF x¸u L ™â 1ë tr¹ gi£i m¢ húu h¤n th¼ sè nguy¶n nhä nh§t tho£ h» thù™ @PFIA gåi l <br /> ë tr¹ gi£i m¢ ™õ— LD sè nguy¶n ˜§t ký thä— h» thù™ @PFIA gåi l  ë tr¹ gi£i m¢ y¸u ™õ— LF<br /> xg÷ñ™ l¤iD n¸u L khæng ™â 1ë tr¹ gi£i m¢ húu h¤n th¼ L gåi l  ™â ë tr¹ gi£i m¢ væ h¤nF<br /> Ætæm—t húu h¤n l  mët ˜ë S A = (Q, Σ, E, I, F )D ð 1âX Q l  tªp húu h¤n ™¡™ tr¤ng th¡iD<br /> Σ l  ˜£ng ™hú ™¡i húu h¤nD E ⊆ Q × Σ × Q l  tªp húu h¤n ™¡™ ™ung @khæng ™hù— ™ung réngAD<br /> I ⊆ Q l  tªp ™¡™ tr¤ng th¡i 1¦uD F ⊆ Q l  tªp ™¡™ tr¤ng th¡i k¸t thó™F<br /> gho ™ung e = (q1 , a, q2 ) ∈ E D t— nâi r¬ng e ríi q1 1¸n q2 D q1 l  1¦u ™õ— e kþ hi»u p[e]D q2<br /> l  ™uèi ™õ— e kþ hi»u n[e]D a l  nh¢n ™õ— e kþ hi»u l[e]F gho q ∈ QD t— kþ hi»u E[q] l  tªp ™¡™<br /> ™ung ríi q F „rong ˜ i ˜¡o n y t— ™án x²t d¤ng ætæm—t húu h¤n mð rëng ™â ™huyºn réngD gåi<br /> t­t l  εEætæm—tD khi m  nh¢n ™õ— mët ™ung e n o 1⠙â thº l  tø réng εF<br /> gho π = e1 · · · ek ∈ E ∗ D ð 1â e1 = (p0 , a1 , p1 ), e2 = (p1 , a2 , p2 ), . . . , ek = (pk−1 , ak , pk )<br /> 1÷ñ™ gåi l  1÷íng 1i tø p0 1¸n pk F wët 1÷íng 1i th nh ™æng trong ætæm—t A l  mët 1÷íng 1i<br /> tø tr¤ng th¡i 1¦u 1¸n tr¤ng th¡i k¸t thó™F „ø w = a1 a2 · · · ak gåi l  nh¢n ™õ— 1÷íng 1i π D tªp<br /> hñp nh¢n ™õ— ™¡™ 1÷íng 1i th nh ™æng trong ætæm—t A gåi l  ngæn ngú 1o¡n nhªn ˜ði AD kþ<br /> hi»u l  L(A)F<br /> <br /> THUŠT TON MÎI XC ÀNH Ë TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY<br /> <br /> 143<br /> <br /> 0ç thà ™â h÷îng G l  mët ™°p G = (V, E)D V l  tªp ™¡™ 1¿nhD E l  tªp ™¡™ ™°p ™â thù tü<br /> gçm h—i ph¦n tû ™õ— V gåi l  ™¡™ ™ungF x¸u e = (u, v) l  ™ung ™õ— 1ç thà ™â h÷îng G th¼ t—<br /> nâi 1¿nh v k· uD t— k½ hi»u N ext(u) = {v ∈ V | (u, v) ∈ E}F x¸u V, E l  húu h¤n th¼ t— gåi G<br /> l  1ç thà húu h¤n ™â h÷îngF<br /> 0÷íng 1i tø 1¿nh u 1¸n 1¿nh v tr¶n 1ç thà ™â h÷îng G l  d¢y 1¿nh x0 , . . . , xn D trong 1â<br /> u = x0 , v = xn , (xi , xi+1 ) ∈ E, i = 0, . . . , n − 1F 0¿nh u gåi l  1¸n 1÷ñ™ 1¿nh v n¸u ™â mët<br /> 1÷íng 1i tø 1¿nh u 1¸n 1¿nh v F<br /> <br /> 3. MËT SÈ GIƒI THUŠT MÐ RËNG ÆTÆMAT<br /> „rong mö™ n yD t— nh­™ l¤i v· ætæm—t thu gån v  xem x²t mët sè kÿ thuªt mð rëng ætæm—t<br /> tø ætæm—t húu h¤n ™ho tr÷î™F g¡™ ætæm—t n y 1÷ñ™ dòng ™ho vi»™ thi¸t k¸ gi£i thuªt t½nh 1ë tr¹<br /> gi£i m¢ ð ph¦n s—uF „r÷î™ ti¶nD v· ætæm—t thu gånX gho ætæm—t húu h¤n A = (Q, Σ, E, I, F )D<br /> mët tr¤ng th¡i q ∈ Q gåi l  1¤t 1÷ñ™ n¸u tçn t¤i 1÷íng 1i tø mët tr¤ng th¡i 1¦u 1¸n q D mët<br /> tr¤ng th¡i q ∈ Q gåi l  1èi 1¤t 1÷ñ™ n¸u tçn t¤i 1÷íng 1i tø q 1¸n mët tr¤ng th¡i k¸t thó™F<br /> Ætæm—t húu h¤n A gåi l  thu gån n¸u t§t ™£ ™¡™ tr¤ng th¡i ™õ— A l  1¤t 1÷ñ™ v  ™ông l <br /> 1èi 1¤t 1÷ñ™F qi£i thuªt kinh 1iºn x¥y düng ætæm—t thu gån 1÷ñ™ thü™ hi»n ˜ði h m kþ hi»u<br /> l  „rim(A)D ™â 1ë phù™ t¤p thíi gi—n l  O(|Q| + |E|) v  L(A) = L(T rim(A))F „i¸p theoD t—<br /> xem x²t mët sè kÿ thuªt mð rëng ætæm—t d÷îi 1¥yF<br /> <br /> 3.1. Ætæmat l÷ïng cüc<br /> Ætæm—t húu h¤n A 1÷ñ™ gåi l  ætæm—t l÷ïng ™ü™ n¸u A ™â mët tr¤ng th¡i 1¦u v  mët<br /> tr¤ng th¡i k¸t thó™ kh¡™ nh—uD khæng ™â ™ung 1¸n tr¤ng th¡i 1¦u v  khæng ™â ™ung ríi tr¤ng<br /> th¡i k¸t thó™F<br /> gho ætæm—t húu h¤n A = (Q, Σ, E, I, F ) 1o¡n nhªn ngæn ngú L = L(A) ⊆ Σ+ F „— x¥y<br /> düng ætæm—t l÷ïng ™ü™ A = (Q , Σ, E , I , F ) 1o¡n nhªn L tø ætæm—t húu h¤n A nh÷ s—u<br /> <br /> i) Q = Q ∪ {s, f }, s, f ∈ Q v  s = f, I = {s}, F = {f }F<br /> /<br /> ii) E = E1 ∪ {(s, a, q) | (p, a, q) ∈ E1 , p ∈ I} vîi E1 = E ∪ {(p, a, f ) | (p, a, q) ∈ E, q ∈ F }F<br /> 0º 1ìn gi£nD t— kþ hi»u A = (Q , Σ, E , s, f ) v  gåi s l  ™ü™ v o @tr¤ng th¡i 1¦uAD f l  ™ü™<br /> r— @tr¤ng th¡i k¸t thó™AF qi£i thuªt x¥y düng ætæm—t l÷ïng ™ü™ A tø ætæm—t húu h¤n A thü™<br /> hi»n ˜ði h m kþ hi»u l  D(A) ™â 1ë phù™ t¤p thíi gi—n O(|Q| + |E|)F<br /> gho ætæm—t l÷ïng ™ü™ A 1o¡n nhªn ngæn ngú L = L(A) ⊆ Σ+ F „— ™â thº x¥y düng<br /> εEætæm—t mð rëng A 1o¡n nhªn L+ @tù™ l  L+ = L(A )AD ˜¬ng ™¡™h ˜ê sung mët ™ung réng<br /> 1i tø ™ü™ r— tîi ™ü™ v o ™õ— AF qi£i thuªt x¥y düng εEætæm—t mð rëng thü™ hi»n ˜ði h m kþ<br /> hi»u l  Ex(A)F<br /> gho εEætæm—t mð rëng A1 = (Q1 , Σ, E1 , s1 , f1 ) 1o¡n nhªn L+ F ˆ²t εEætæm—t A2 =<br /> (Q2 , Σ, E2 , s2 , f2 )D ð 1â Q2 = {s2 }, s2 = f2 @A2 ™â duy nh§t mët tr¤ng th¡iD vø— l  tr¤ng<br /> th¡i 1¦u v  ™ông l  tr¤ng th¡i k¸t thó™AD E2 ™â |Σ| + 1 ™ung 1i tø tr¤ng th¡i duy nh§t trong<br /> A2 1¸n ™h½nh nâ vîi nh¢n l  kþ tü thuë™ Σ ∪ {ε}D t— ™â Σ∗ = L(A2 )F „— x¥y düng εEætæm—t<br /> gh²p A = (Q, Σ, E, s, f )D ˜¬ng ™¡™h ˜ê sung mët ™ung réng 1i tø tr¤ng th¡i k¸t thó™ ™õ— A1<br /> 1¸n tr¤ng th¡i duy nh§t ™õ— A2 D t— l§y Q = Q1 ∪ Q2 , E = E1 ∪ E2 ∪ (f1 , ε, f2 ), s = s1 , f = f2 D<br /> tr¤ng th¡i f1 gåi l  tr¤ng th¡i gh²p trong εEætæm—t gh²p AF εEætæm—t gh²p A 1o¡n nhªn ngæn<br /> ngú L+ Σ∗ D gi£i thuªt x¥y düng εEætæm—t gh²p thü™ hi»n ˜ði h m kþ hi»u l  Graft @A1 AF<br /> <br /> 144<br /> <br /> NG QUY˜T THNG, NGUY™N œNH H…N, PHAN TRUNG HUY<br /> <br /> Nhªn x²t 3.1. Cho ætæmat húu h¤n A = (Q, Σ, E, I, F ) vîi c = |Σ| l  h¬ng sè. Khi â,<br /> sè tr¤ng th¡i cõa D(A), Ex(D(A)) v  Graf t(Ex(D(A))) khæng qu¡ |Q| + 3 do â câ cï<br /> O(|Q|). Sè cung cõa D(A) khæng qu¡ 4|E|, cõa Ex(D(A)) khæng qu¡ 4|E| + 1 v  cõa<br /> Graf t(Ex(D(A))) khæng qu¡ 4|E| + c + 3, do â công câ cï O(|E|).<br /> <br /> 3.2. Ætæmat t½ch<br /> €h²p l§y t½™h ætæm—t @xem ‘TD U“A 1÷ñ™ sû döng trong nhi·u ùng döng 1º t¤o r— ætæm—t<br /> phù™ hñp tø nhúng ætæm—t 1ìn gi£nF gho h—i εEætæm—t mð rëngD h—y εEætæm—t gh²p nh÷ 1¢<br /> x²t ð tr¶nD A1 = (Q1 , Σ, E1 , s1 , f1 ) v  A2 = (Q2 , Σ, E2 , s2 , f2 )F uhi 1âD t½™h ™õ— A1 v  A2 l <br /> εEætæm—t kþ hi»u P rod(A1 , A2 ) = (Q, Σ, E, (s1 , s2 ), (f1 , f2 ))D trong 1â Q ⊆ Q1 × Q2 D E 1÷ñ™<br /> x¡™ 1ành theo quy t­™ s—uX<br /> <br /> i) ∀(q1 , a, p1 ) ∈ E1 , ∀(q2 , a, p2 ) ∈ E2 , a ∈ Σ th¼ ((q1 , q2 ), a, (p1 , p2 )) ∈ E Y<br /> ii) ∀(q1 , ε, p1 ) ∈ E1 , ∀(q2 , ε, p2 ) ∈ E2 th¼ ((q1 , q2 ), ε, (p1 , p2 )) ∈ E Y<br /> iii) ∀(q1 , ε, p1 ) ∈ E1 , ∀(q2 , a, p2 ) ∈ E2 , a ∈ Σ th¼ ((q1 , q2 ), ε, (p1 , q2 )) ∈ E Y<br /> iv) ∀(q1 , a, p1 ) ∈ E1 , ∀(q2 , ε, p2 ) ∈ E2 , a ∈ Σ th¼ ((q1 , q2 ), ε, (q1 , p2 )) ∈ E Y<br /> v) E ™h¿ ™hù— ™¡™ ™ung 1¢ x²t ð ˜èn tr÷íng hñp tr¶nF<br /> qi£i thuªt ™â thº ˜­t 1¦u tø tr¤ng th¡i (s1 , s2 )D rçi thü™ hi»n theo quy t­™ ð tr¶n x¡™ 1ành<br /> ™¡™ tr¤ng th¡i v  ™ung ™õ— ætæm—t t½™hF h÷îi 1¥y l  gi£i thuªtF<br /> <br /> Function Prod@A1D A2A<br /> InputX A1D A2 l  εEætæm—t mð rëngD ho°™ εEætæm—t gh²pF<br /> OutputX εEætæm—t A = (Q, Σ, E, s, f ) l  t½™h ™õ— A1 v  A2F<br /> <br /> {S l  h ng ñi, CQpush, CQPop l  ph²p bê sung v  lo¤i bä mët ph¦n tû tr¶n S .}<br /> IF<br /> Q = {(s1 , s2 )}Y gpush(S, (s1 , s2 ))Y<br /> s = (s1 , s2 ); f = (f1 , f2 ); E = ∅;<br /> PF<br /> while S = ∅ do<br /> QF<br /> (q1 , q2 ) ←− g€op@S AY<br /> RF<br /> for e—™h (e1 , e2 ) in E[q1 ] × E[q2 ] do<br /> SF<br /> t = true; label = ε;<br /> TF<br /> ™—se<br /> l[e1 ] = l[e2 ] ∧ l[e1 ] = ε : (p1 , p2 ) = (n[e1 ], n[e2 ]); label = l[e1 ];<br /> l[e1 ] = l[e2 ] = ε : (p1 , p2 ) = (n[e1 ], n[e2 ]);<br /> l[e1 ] = ε ∧ l[e2 ] = ε : (p1 , p2 ) = (n[e1 ], q2 );<br /> l[e1 ] = ε ∧ l[e2 ] = ε : (p1 , p2 ) = (q1 , n[e2 ]);<br /> else t = f alse;<br /> UF<br /> end ™—seY<br /> VF<br /> if t = true then {N¸u (p1 , p2 ) ∈ Q th¼ Q = Q ∪ (p1 , p2 )}<br /> /<br /> if felong(p1 , p2 ) = 0 then<br /> felong(p1 , p2 ) = 1Y<br /> g€ush(S, (p1 , p2 ))Y<br /> <br /> THUŠT TON MÎI XC ÀNH Ë TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY<br /> WF<br /> <br /> return AF<br /> <br /> 145<br /> <br /> E = E ∪ {((q1 , q2 ), label, (p1 , p2 ))}Y<br /> <br /> i) T÷ìng tü nh÷ ph¥n t½ch cõa Mohri trong [6, 7], gi£i thuªt câ ë phùc<br /> t¤p thíi gian l  O((|Q1| + |E1|)(|Q2| + |E2|)).<br /> <br /> Nhªn x²t 3.2.<br /> <br /> ii)<br /> <br /> Cho A2 = (Q2, Σ, E2, s2, f2) l  ε-ætæmat mð rëng o¡n nhªn L+. ε-ætæmat gh²p A1 =<br /> Graf t(A2 ) = (Q1 , Σ, E1 , s1 , f1 ) câ tr¤ng th¡i gh²p fG (ð â ta êi t¶n tr¤ng th¡i gh²p<br /> tø f2 th nh fG, tr¤ng th¡i ¦u tø s2 th nh s1). Tr¶n ε-ætæmat t½ch P rod(A1, A2), nh¢n<br /> cõa ÷íng i giúa hai tr¤ng th¡i k¸ ti¸p (fG, qi) v  (fG, qj ) (ho°c (pi, f2) v  (pj , f2),<br /> ho°c (s1, qi) v  (fG, qj ), ho°c (pi, s2) v  (pj , f2)) l  tø thuëc L.<br /> <br /> 4. XC ÀNH Ë TR™ GIƒI M‚ CÕA NGÆN NGÚ CHNH QUY<br /> gho ngæn ngú ™h½nh quy L 1÷ñ™ 1o¡n nhªn ˜ði ætæm—t húu h¤n AD 1º x¡™ 1ành 1ë tr¹<br /> gi£i m¢ ™õ— LD tr÷î™ h¸t t— gi£i quy¸t ˜ i to¡n ˜ê trñ tr¶n 1ç thà nh÷ d÷îi 1¥yF<br /> <br /> 4.1. B i to¡n v· chu tr¼nh hñp l» tr¶n ç thà<br /> gho 1ç thà húu h¤n ™â h÷îng @™â thº ™â khuy¶nA G = (V, E) vîi h—i 1¿nh 1°™ ˜i»t l  1¿nh<br /> khði 1¦u s v  1¿nh k¸t thó™ f (s = f )D tªp U ⊆ V gåi l  tªp 1¿nh kh◠@1¿nh s v  f khæng<br /> thuë™ tªp U AD ™¡™ 1¿nh ™án l¤i gåi l  1¿nh khæng khâ—F<br /> gho 1÷íng 1i π gçm d¢y 1¿nh v1 , . . . , vj , . . . , vi , . . . , vk @vîi s = v1 A tr¶n 1ç thà GF x¸u ™â<br /> 1 < i < k s—o ™ho vi ∈ U, vk = vj , 1 ≤ j ≤ i th¼ π gåi l  chu tr¼nh hñp l» tr¶n 1ç thà GF 0¿nh<br /> vl , j ≤ l ≤ k gåi l  ¿nh trong ™õ— ™hu tr¼nh hñp l»F 0÷íng 1i π gåi l  i qua 1¿nh v D n¸u v<br /> l  mët trong ™¡™ 1¿nh vl , 2 ≤ l ≤ k F π ™ông 1÷ñ™ gåi l  chùa 1¿nh v D n¸u v l  mët trong ™¡™<br /> 1¿nh vl , 1 ≤ l ≤ k F<br /> <br /> B i to¡n 1. gho 1ç thà húu h¤n ™â h÷îng G = (V, E) nh÷ ð tr¶nF gho ˜i¸t tr¶n G ™â tçn<br /> t¤i ™hu tr¼nh hñp l» h—y khængF<br /> <br /> 0º gi£i ˜ i to¡n tr¶nD tr÷î™ h¸t t— x¥y düng 1ç thà s—o ™h²p G = (V , E ) tø 1ç thà<br /> G = (V, E) nhí kÿ thuªt s—o ™h²p 1ç thà nh÷ s—uX<br /> <br /> i) †îi v ∈ V s—o ™h²p th nh h—i 1¿nh (v, 1), (v, 2) ™õ— V F<br /> ii) †îi (u, v) ∈ E X<br /> C ƒ—o ™h²p th nh h—i ™ung ((u, 1), (v, 1)), ((u, 2), (v, 2)) ™õ— E Y<br /> C x¸u u ∈ U th¼ ˜ê sung ™ung ((u, 1), (v, 2)) v o E Y<br /> r m x¥y düng 1ç thà s—o ™h²p G kþ hi»u l  ˆgopy(G)D d÷îi 1¥y l  gi£i thuªtX<br /> <br /> Function XCopy(G)<br /> <br />