銆婄紪璇戝師鐞嗐�嬬粌涔犻涓�
涓�銆佸～绌洪锛堟瘡绌?/p>
1
鍒嗭級
1
锛庤
G
锛?/p>
S
锛芥槸涓�涓枃娉曪紝鎴戜滑鎶婅兘鐢辨枃娉曠殑
锛?/p>
1
锛?/p>
鎺ㄥ鍑烘潵鐨勭鍙蜂覆
伪
绉?/p>
涓?/p>
G
鐨勪竴涓彞鍨嬨�傚綋鍙ュ瀷
伪
浠呯敱
锛?/p>
2
锛?/p>
缁勬垚鏃?/p>
(
鍗?/p>
伪鈭?/p>
V
T
*
)
锛屽垯灏嗗畠绉颁负
G
浜х敓
鐨勫彞瀛愩�?/p>
2
锛庝粠鏌愪竴缁欏畾鐨勭姸鎬?/p>
q
鍑哄彂锛屼粎缁忚繃鑻ュ共鏉?/p>
(3)
鐨勭煝绾挎墍鑳借揪鍒扮殑鐘舵�佹墍缁?/p>
鎴愮殑闆嗗悎绉颁负
蔚
-CLOSURE(q)
銆?/p>
3
锛庤
G=(V
N
,V
T
,P,S)
鏄竴鏂囨硶锛屾垜浠
G
涓殑涓�涓鍙?/p>
X
鈭?/p>
V
N
鈭?/p>
V
T
鏄湁鐢ㄧ殑锛屾槸鎸?/p>
X
鑷?/p>
灏戝嚭鐜板湪
锛?/p>
4
锛?/p>
鐨勬帹瀵艰繃绋嬩腑锛屽惁鍒欙紝灏辫
X
鏄棤鐢ㄧ殑銆傛垜浠皢涓嶅惈褰㈠
A鈫扐
鐨?/p>
浜х敓寮忓拰涓嶅惈鏃犵敤绗﹀彿鍙婃棤鐢ㄤ骇鐢熷紡鐨勬枃娉曠О涓?/p>
锛?/p>
5
锛?/p>
銆?/p>
4
锛庢垜浠父閲囩敤褰㈠
(class, value)
鐨勪簩鍏冨紡浣滀负涓�涓崟璇嶇殑
(6)
銆傚叾
涓?/p>
,class
鏄竴涓暣鏁帮紝鐢ㄦ潵鎸囩ず璇ュ崟璇嶇殑
(7)
锛?/p>
value
鍒欐槸鍗曡瘝涔嬪�笺�?/p>
5
锛庝竴涓枃娉?/p>
G[S]
鍙〃绀烘垚褰㈠
锛?/p>
8
锛?/p>
鐨勫洓鍏冨紡銆傚叾涓?/p>
V
N
,V
T
,P
鍧囦负闈炵┖鐨?/p>
鏈夐檺闆嗭紝
鍒嗗埆绉颁负闈炵粓缁撶鍙烽泦銆?/p>
缁堢粨绗﹀彿闆嗗拰浜х敓寮忛泦锛?/p>
S
鈭?/p>
V
N
涓烘枃娉曠殑寮�濮嬬鍙枫�?/p>
姝ゅ锛?/p>
灏嗗嚭鐜板湪鍚勪骇鐢熷紡宸﹂儴鍜屽彸閮ㄧ殑涓�鍒囩鍙锋墍缁勬垚鐨勯泦鍚堢О涓?/p>
锛?/p>
9
锛?/p>
锛岃浣?/p>
V
銆?/p>
鏄剧劧锛?/p>
V=V
N
鈭?/p>
V
T
,V
N
鈭￢
T
=
飪?/p>
銆?/p>
6
锛庨�氬父锛屽彲閫氳繃涓ょ閫斿緞鏉ユ瀯閫犺瘝娉曞垎鏋愮▼搴忋�傚叾涓�鏄牴鎹璇█涓悇绫诲崟璇嶇殑鏌愮
鎻忚堪鎴栧畾涔夛紝鐢?/p>
(10)
鏋勯�犺瘝娉曞垎鏋愮▼搴忥紱鍙﹀涓�绉嶉�斿緞鏄墍璋撹瘝娉曞垎鏋愮▼搴忕殑
(11)
銆?/p>
7
锛庤
G
涓轰竴鏂囨硶锛孉鈫捨?/p>
鏄?/p>
G
鐨勪竴涓骇鐢熷紡锛屽鏋?/p>
伪
鍏锋湁
蠀A未
鐨勫舰寮忥紝鍏朵腑
蠀锛屛?/p>
涓嶅悓鏃朵负
蔚锛屽垯绉颁骇鐢熷紡
A鈫捨?/p>
鏄?/p>
锛?/p>
12
锛?/p>
銆傝嫢瀛樺湪鎺ㄥ
飦?
飦?/p>
飦?/p>
A
A
*
飪?/p>
飪?/p>
锛屽垯
绉颁骇鐢熷紡
A鈫捨?/p>
鏄?/p>
锛?/p>
13
锛?/p>
銆?/p>
8
锛庤
M=(K,危,f,S
0
,Z)
涓轰竴
DFA
锛屽苟璁?/p>
s
鍜?/p>
t
鏄?/p>
M
鐨勪袱涓笉鍚岀姸鎬侊紝鎴戜滑璇寸姸鎬?/p>
s,t
涓?/p>
鏌愪竴杈撳叆涓?/p>
w (14)
锛屾槸鎸囦粠
s,t
涓箣涓�鍑哄彂锛屽綋鎵瀹?/p>
w
涔嬪悗鍒拌揪
M
鐨勭粓鎬侊紝浣?/p>
浠庡叾涓殑鍙︿竴涓姸鎬佸嚭鍙戯紝褰撴壂瑙嗗畬鍚屼竴涓?/p>
w
鍚庤�岃繘鍏?/p>
(15)
銆?/p>
9
锛庢妸鏈�鍙虫帹瀵肩О涓?/p>
锛?/p>
16
锛?/p>
锛岃�屾妸鍙冲彞鍨嬬О涓?/p>
锛?/p>
17
锛?/p>
銆?/p>
10
锛庡鏋滀粠鐘舵�佽浆鎹㈠浘鐨勫垵鎬佸嚭鍙戯紝鍒嗗埆娌跨潃涓�鍒囧彲鑳界殑璺緞鍒拌揪
(18)
锛屽苟