Ng i tri nh ba y: ươ
TS. Hoa ng Manh Thăng
Tôi thiêu hoa trang thai
V i FSM đn gian thi co thê dê thây qua s đô ơ ơ ơ
trang tha i ma sô trang tha i đc du ng co thê tôi ươ
thiêu ho a
V i FSM ph c tap, s đô trang tha i co thê co ơ ư ơ
nhiêu trang tha i cân đê th c hiên ch c năng yêu ư ư
câu
Tôi thiêu ho a ca c trang tha i đc quan tâm đê tôi ươ
thiêu ho a mach
Thay vi cô đa ra ca c trang tha i na o t ng đng, ư ươ ươ
th ng dê h n đa ra ca c trang tha i không t ng ươ ơ ư ươ
đng ươ đinh nghi a thu tuc tôi u ư
Trang thai tương đương
Hai trang tha i Si va Sj la t ng nêu đô i v i moi ươ ơ
chuôi va o co thê, chu ng cho ra cu ng môt gia tri
đâ u ra không quan tâm đê n S i hay Sj la trang tha i
đâ u
Nêu đâ u va o w=0 đa va o FSM khi đang Sư ơ i va
FSM dich sang Su, thi Su đc đăt la ươ 0-successor cua
Si
T ng t , nêu ươ ư w=1 va FSM chuyên sang Sy thi Sy
đc goi la 1-successor cua Sươ i
Ca c successor cua Si la k-successor cua no , v i ơ
nhiêu biên va o
Tôi thiêu hoa phân tach nho
T đinh nghi a vê t ng đng, nêu S_i va S_j la ư ươ ươ
t ng đng thi t ng ng co ươ ươ ươ ư k-successor t ng ươ
đngươ
No đc du ng tao ra thu tuc tôi thiêu ho a liên quan ươ
đê n ca c trang tha i nh la ca c tâp va sau đo pha v ư ơ
ca c tâp đo tha nh ca c partitions gôm ca c tâp con không
t ng đngươ ươ
Đinh nghi a: môt partition gôm môt hay nhiêu bloc, mô
block gôm môt tâp con ca c trang tha i co thê la t ng ươ
đng, nh ng ca c trang tha i trong môt block không ươ ư
t ng đng v i ca c trang tha i trong block kha c ươ ươ ơ
Vi du tôi thiêu hoa partition
Xem bang trang tha i sau
Partition ban đâ u gôm tâ ca ca c trang tha i