Bài báo đề xuất một giải thuật mới xác định độ trễ giải mã của ngôn ngữ chính quy được đón nhận với ôtômat hữu hạn A. Giải thuật có độ phức tạp O(n3) với n là số cung và trạng thái của A. nội dung chi tiết. | T¤p ch½ Tin håc v i·u khiºn håc, , (2012), 141-152 THU T TO N MÎI X C ÀNH Ë TR GI I M CÕA NGÆN NGÚ CH NH QUY 0 xq r xq1 D xq x 0 xr r x2 D rex xq r 3 1 Tr÷íng ¤i håc S÷ ph¤m Kÿ thuªt Nam ành 2 Tr÷íng ¤i håc S÷ ph¤m Kÿ thuªt H÷ng Y¶n 3 Tr÷íng ¤i håc B¡ch khoa H Nëi 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÷ñ 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 v tr¤ng th¡i õ AF Abstract. sn this p perD we propose new lgorithm determining de iphering del y of regul r l ngu geD whi h re ognizes y finite utom ton AF he lgorithm h s time omplexity O(n3 )D where n is the num er of st tes nd edges of AF 1. GIÎI THI U 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 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¡ 1ành mët ¡ h h hn l kh¡ nh uF uho£ng thíi gi n tr¹ n y 1÷ñ h¼nh thù hâ ¬ng 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 ¡ æng tr¼nh õ qil ert nd woore @IWSWA @xem W AD õ vevenshtein @IWTRA @xem IH AF îi 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¹ 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¢ 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¡ 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 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 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÷ õ w rkov @IWTPA @xem IP AD h¤tzen erger @IWTTA @xem II AD ghoffrut @IWUWA @xem IQ AD u vF t iger @IWVTA @xem S AD tF hevolder @IWWRA @xem Q AD t vros uonst ntinidis @PHHPA @xem V AD F F ruyE F F x m @PHHPA @xem IR AD hF vF n
