การลดขนาด DFA
การลดขนาด DFA โดยใช้ Myphill-Nerode Theorem
อัลกอริทึม
Input - DFA
Output - ย่อขนาด DFA
Step 1- วาดตารางสำหรับทุกคู่ของสถานะ (Q i , Q j ) ไม่จำเป็นต้องเชื่อมต่อโดยตรง [ทั้งหมดจะไม่มีเครื่องหมายในตอนแรก]
Step 2- พิจารณาทุกคู่สถานะ (Q i , Q j ) ใน DFA โดยที่ Q i ∈ F และ Q j ∉ F หรือกลับกันแล้วทำเครื่องหมาย [ที่นี่ F คือชุดของสถานะสุดท้าย]
Step 3 - ทำซ้ำขั้นตอนนี้จนกว่าเราจะไม่สามารถทำเครื่องหมายสถานะได้อีกต่อไป -
หากมีคู่ที่ไม่มีเครื่องหมาย (Q i , Q j ) ให้ทำเครื่องหมายว่าคู่ {δ (Q i , A), δ (Q i , A)} ถูกทำเครื่องหมายไว้สำหรับตัวอักษรอินพุตบางตัว
Step 4- รวมคู่ที่ไม่มีเครื่องหมายทั้งหมด (Q i , Q j ) และทำให้เป็นสถานะเดียวใน DFA ที่ลดลง
ตัวอย่าง
ให้เราใช้อัลกอริทึม 2 เพื่อย่อ DFA ที่แสดงด้านล่าง
Step 1 - เราวาดตารางสำหรับทุกคู่ของรัฐ
| ก | ข | ค | ง | จ | ฉ | |
| ก | ||||||
| ข | ||||||
| ค | ||||||
| ง | ||||||
| จ | ||||||
| ฉ |
Step 2 - เราทำเครื่องหมายคู่สถานะ
| ก | ข | ค | ง | จ | ฉ | |
| ก | ||||||
| ข | ||||||
| ค | ✔ | ✔ | ||||
| ง | ✔ | ✔ | ||||
| จ | ✔ | ✔ | ||||
| ฉ | ✔ | ✔ | ✔ |
Step 3- เราจะพยายามทำเครื่องหมายคู่สถานะด้วยเครื่องหมายถูกสีเขียวตามสกรรมกริยา หากเราป้อน 1 เพื่อระบุ 'a' และ 'f' มันจะไปที่สถานะ 'c' และ 'f' ตามลำดับ (c, f) ถูกทำเครื่องหมายไว้แล้วดังนั้นเราจะทำเครื่องหมายคู่ (a, f) ตอนนี้เราป้อน 1 เพื่อระบุ 'b' และ 'f'; มันจะไปที่สถานะ 'd' และ 'f' ตามลำดับ (d, f) ถูกทำเครื่องหมายไว้แล้วดังนั้นเราจะทำเครื่องหมายคู่ (b, f)
| ก | ข | ค | ง | จ | ฉ | |
| ก | ||||||
| ข | ||||||
| ค | ✔ | ✔ | ||||
| ง | ✔ | ✔ | ||||
| จ | ✔ | ✔ | ||||
| ฉ | ✔ | ✔ | ✔ | ✔ | ✔ |
หลังจากขั้นตอนที่ 3 เรามีชุดค่าผสมของสถานะ {a, b} {c, d} {c, e} {d, e} ที่ไม่มีเครื่องหมาย
เราสามารถรวม {c, d} {c, e} {d, e} เป็น {c, d, e}
ดังนั้นเราจึงมีสองสถานะรวมกันคือ - {a, b} และ {c, d, e}
ดังนั้น DFA ที่ย่อขนาดสุดท้ายจะมีสามสถานะ {f}, {a, b} และ {c, d, e}
การย่อขนาด DFA โดยใช้ทฤษฎีบทความเท่าเทียมกัน
หาก X และ Y เป็นสองสถานะใน DFA เราสามารถรวมสองสถานะนี้เป็น {X, Y} ได้หากไม่สามารถแยกแยะได้ สองสถานะสามารถแยกแยะได้หากมีอย่างน้อยหนึ่งสตริง S เช่นหนึ่งในδ (X, S) และδ (Y, S) ยอมรับและอีกสถานะหนึ่งไม่ยอมรับ ดังนั้น DFA จึงมีน้อยมากก็ต่อเมื่อทุกรัฐสามารถแยกแยะได้
อัลกอริทึม 3
Step 1 - ทุกรัฐ Q แบ่งออกเป็นสองพาร์ติชัน - final states และ non-final states และแสดงโดย P0. ทุกรัฐในพาร์ทิชัน 0 THเทียบเท่า ใช้เคาน์เตอร์k และเริ่มต้นด้วย 0
Step 2- เพิ่ม k โดย 1 สำหรับแต่ละพาร์ติชันใน P kให้แบ่งสถานะใน P kออกเป็นสองพาร์ติชั่นถ้าแยกได้ k สองสถานะภายในพาร์ติชัน X และ Y นี้สามารถแยกความแตกต่าง k ได้หากมีอินพุตS ดังนั้น δ(X, S) และ δ(Y, S) เป็น (k-1) - แยกแยะได้
Step 3- หาก P k ≠ P k-1ให้ทำซ้ำขั้นตอนที่ 2 มิฉะนั้นไปที่ขั้นตอนที่ 4
Step 4- นวด k THชุดเทียบเท่าและทำให้พวกเขารัฐใหม่ของการลดลง DFA
ตัวอย่าง
ให้เราพิจารณา DFA ต่อไปนี้ -
| q | δ (q, 0) | δ (q, 1) |
|---|---|---|
| ก | ข | ค |
| ข | ก | ง |
| ค | จ | ฉ |
| ง | จ | ฉ |
| จ | จ | ฉ |
| ฉ | ฉ | ฉ |
ให้เราใช้อัลกอริทึมข้างต้นกับ DFA ข้างต้น -
- P 0 = {(c, d, e), (a, b, f)}
- ป1 = {(c, d, e), (a, b), (f)}
- ป2 = {(c, d, e), (a, b), (f)}
ดังนั้น P 1 = P 2
DFA ที่ลดลงมีสามสถานะ DFA ที่ลดลงมีดังนี้ -
| ถาม | δ (q, 0) | δ (q, 1) |
|---|---|---|
| (ก, ข) | (ก, ข) | (ค, ง, จ) |
| (ค, ง, จ) | (ค, ง, จ) | (ฉ) |
| (ฉ) | (ฉ) | (ฉ) |