การสร้างเพาเวอร์เซต

ในทฤษฎีการคำนวณและทฤษฎีออโตมาต้าเป็นการสร้างเซตย่อยของเพาเวอร์เซตเป็นวิธีการมาตรฐานสำหรับการแปลงค่าสถานะจำกัดหรือสถานะที่ไม่จำกัดก็ได้ ซึ่งจำเป็นต่อการใช้ในภาษาทางการ เป็นทฤษฎีที่สำคัญเพราะมีการระบุว่า (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.

สถานะเริ่มต้นของ (DFA) ที่สร้างขึ้นจาก (NFA) นี้คือชุดของสถานะ (NFA) ทั้งหมดที่สามารถเข้าถึงได้จากสถานะ 1 โดยการε-moves นั่นคือชุด {1,2,3} การเปลี่ยนจาก {1,2,3} โดยใช้สัญลักษณ์ป้อน 0 ต้องเป็นไปตามที่ลูกศรจากสถานะ  1 ถึงสถานะ 2 หรือลูกศรจากสถานะ  3 ถึงสถานะ  4. นอกจากนี้สถานะ ทั้ง 2 และสถานะ 4 ยังไม่ได้ ε-movesดังนั้น T ({1,2,3}, 0) = {2,4} และด้วยเหตุผลเดียวกัน (DFA) ที่สร้างขึ้นทั้งหมดจาก (NFA) มีดังที่แสดงด้านล่าง

168x168px

ในตัวอย่างนี้เราจะเพาเวอร์เซตซึ่งเท่ากับ 2 ยกกำลัง n และ n = 4 ดังนั้นจะเพาเวอร์เซตทั้งหมด 2 ยกกำลัง 4 = 16 สถานะ ซึ่งได้มีสถานะ 5 สถานะที่สามารถเข้าถึงได้จากสถานะเริ่มต้นของ DFA ส่วนที่เหลืออีก 11 วถานะในเพาเวอร์เซตของชุด(NFA)จะไม่สามารถเข้าถึงได้ ตัวอย่างการเขียนโปรแกรม

def Powerset(data):
    result = []
    for i in data:
        newsubsets = [subset + [i] for subset in result]
        result.extend(newsubsets)
    return result