เร็วกว่าเบราว์เซอร์!การสร้างเพาเวอร์เซต
ในทฤษฎีการคำนวณและทฤษฎีออโตมาต้าเป็นการสร้างเซตย่อยของเพาเวอร์เซตเป็นวิธีการมาตรฐานสำหรับการแปลงค่าสถานะจำกัดหรือสถานะที่ไม่จำกัดก็ได้ ซึ่งจำเป็นต่อการใช้ในภาษาทางการ เป็นทฤษฎีที่สำคัญเพราะมีการระบุว่า (NFAs) แม้จะมีความยืดหยุ่นเพิ่มเติมแต่ก็ไม่สามารถรับรู้ภาษาใด ๆ ที่ (DFA) บางตัวไม่สามารถรับรู้ได้นอกจากนี้ยังเป็นสิ่งสำคัญในทางปฏิบัติสำหรับการแปลง (NSAs) ที่ง่ายต่อการสร้างให้เป็น(DFAs) ที่มีประสิทธิภาพมากขึ้น อย่างไรก็ตาม หาก (NFA) มี n สถานะ (DFAs) ที่เป็นผล อาจมีสถานะได้ถึง 2 สถานะตัวเลข ฟังก์ชันเลขชี้กำลังที่มีจำนวนมากบางครั้งอาจทำให้การสร้างเป็นไปไม่ได้สำหรับ (NFAs) ที่มีจำนวนมาก การสร้างบางครั้งเรียกว่า Rabin-Scott powerset construction (หรือpowerset construction) เพื่อแยกความแตกต่างจากโครงสร้างที่คล้ายกันสำหรับออโตมาต้าประเภทอื่น ๆ ได้รับการตีพิมพ์เป็นครั้งแรกโดย Michael O. Rabin และ Dana Scott ในปี 1959 160x160px การสร้างเพาเวอร์เซต ในการสร้างเพาเวอร์เซตของสถานะทั้งหมดของ (DFA) คือ เพาเวอร์เซตของ Q ของเซ็ตย่อยที่เป็นไปได้ทั้งหมดของ Q อย่างไรก็ตามหลายสถานะของ (DFA) ที่เป็นผลอาจไม่มีประโยชน์เนื่องจากอาจไม่สามารถเข้าถึงได้จาก สถานะเริ่มต้น อีกทางเลือกหนึ่งของการก่อสร้างสร้างเฉพาะสถานะที่สามารถเข้าถึงได้จริง ตัวอย่าง (NFA) ด้านล่างมี 4 สถานะ สถานะ 1 เป็นค่าเริ่มต้นและสถานะ 3 และ 4 เป็นตัวอักษรที่ประกอบด้วย 2 สัญลักษณ์ คือ 0 และ1 และมีการ ε-moves.
0 ความสัมพันธ์
