การแปลง NDFA เป็น DFA

คำชี้แจงปัญหา

ปล่อย X = (Q_x, ∑, δ_x, q₀, F_x)เป็น NDFA ซึ่งยอมรับภาษา L (X) เราต้องออกแบบ DFA ที่เทียบเท่าY = (Q_y, ∑, δ_y, q₀, F_y) ดังนั้น L(Y) = L(X). ขั้นตอนต่อไปนี้แปลง NDFA เป็น DFA ที่เทียบเท่า -

อัลกอริทึม

Input - NDFA

Output - DFA ที่เทียบเท่า

Step 1 - สร้างตารางสถานะจาก NDFA ที่กำหนด

Step 2 - สร้างตารางสถานะว่างภายใต้ตัวอักษรอินพุตที่เป็นไปได้สำหรับ DFA ที่เทียบเท่า

Step 3 - ทำเครื่องหมายสถานะเริ่มต้นของ DFA ด้วย q0 (เหมือนกับ NDFA)

Step 4- ค้นหาการรวมกันของ States {Q ₀ , Q ₁ , ... , Q _n } สำหรับตัวอักษรที่ป้อนได้แต่ละตัว

Step 5 - ทุกครั้งที่เราสร้างสถานะ DFA ใหม่ภายใต้คอลัมน์ตัวอักษรอินพุตเราต้องใช้ขั้นตอนที่ 4 อีกครั้งมิฉะนั้นให้ไปที่ขั้นตอนที่ 6

Step 6 - รัฐที่มีสถานะสุดท้ายของ NDFA เป็นสถานะสุดท้ายของ DFA ที่เทียบเท่า

ตัวอย่าง

ให้เราพิจารณา NDFA ที่แสดงในรูปด้านล่าง

q	δ (q, 0)	δ (q, 1)
ก	{a, b, c, d, e}	{d, e}
ข	{ค}	{e}
ค	∅	{b}
ง	{e}	∅
จ	∅	∅

เมื่อใช้อัลกอริทึมข้างต้นเราจะพบ DFA ที่เทียบเท่า ตารางสถานะของ DFA แสดงอยู่ด้านล่าง

q	δ (q, 0)	δ (q, 1)
[a]	[a, b, c, d, e]	[d, e]
[a, b, c, d, e]	[a, b, c, d, e]	[b, d, e]
[d, e]	[e]	∅
[b, d, e]	[c, e]	[e]
[e]	∅	∅
[c, e]	∅	[b]
[b]	[ค]	[e]
[ค]	∅	[b]

แผนภาพสถานะของ DFA มีดังนี้ -