วิธีแปลง NFA ให้ไปเป็น FA

วิธีแปลง Non-deterministic Finite Automata (NFA) ให้เป็น Deterministic Finite Automata (DFA) แต่ผมขอเรียกสั้นๆ ว่า FA นะครับ (เพราะมันไม่มี N) ทั้งนี้ ถ้ามีเส้นที่เป็น Λ คือเส้นซึ่งสามารถไปต่อได้โดยไม่ต้องอ่านตัวอักษรเข้ามา (ค่อยไปอ่านที่หลังใน state ถัดๆ ไป) ก็คือ NFA ของเราเป็นแบบ NFA-Λ ก็ต้องเปลี่ยนมันให้เป็น NFA ที่ไม่มี Λ เสียก่อน วิธีการจะขอกล่าวในภายหลังนะครับ ตอนนี้ขอแบบ NFA ไม่มี Λ ก่อน

การแปลงเราจะสร้างตารางที่คอลัมน์เป็นตัวอักษรที่จะเป็น input เข้ามาได้ ส่วนแถวจะเป็น state ของ FA ที่เราจะค่อยๆ สร้างขึ้นมาใหม่จาก NFA โดยชื่อ state ที่สร้างขึ้นใหม่นี้ จะเป็น set ที่ได้จากการประสมชื่อของ state จาก NFA ทำให้จำนวน state ใหม่ของ FA นี้ อาจพุ่งไปได้สูงสุดเท่ากับ 2 ยกกำลังจำนวน state ของ NFA ถ้าพูดแบบคณิตศาสตร์แล้ว state ของ FA ที่สร้างขึ้นมาใหม่ ก็คือ subset ของ set ที่มี state ทั้งหมดของ NFA และเพราะว่าเป็น set ทำให้ลำดับของชื่อ state ที่ได้จาก NFA นั้นไม่มีความสำคัญ ตัวอย่างเช่น {0, 1} เท่ากับ {1, 0}

ให้เราเริ่มจาก state แรกเริ่มต้นก่อน (ตั้งต้น) ซึ่งชื่อ state จะเป็น set ที่มีสมาชิกเป็น state เริ่มต้นจาก NFA ใส่ในแถวแรกของตาราง จากนั้นไล่แต่ละ state ใน set นั้น (กรณีนี้ มีแต่ state เริ่มต้น) ว่าตัวอักษรนั้นๆ ไปยัง state ไหนได้บ้าง ก็ให้เอา state ที่ไปได้นั้น มาเพิ่มใน set ที่เป็น state ใหม่ ที่อยู่ภายใต้ตัวอักษรนั้นๆ ขั้นต่อมา

จากนั้นจะมี set ของ state เกิดขึ้นมา ก็เอาไปใส่ในแถวถัดไป แล้วแก้โจทย์แบบเดิมต่อ จนกว่าจะไม่มี set ของ state ให้แก้โจทย์อีก

ตัวอย่างนะครับ

nfa01

ถ้าจะเขียนเป็นตารางแสดงวิธีการเปลี่ยน state ของ NFA นี้ (WordPress.com ทำตารางยังไงเนี้ย)

state  | a | b
0 | 1 | 2
1 | 1,2 | 2
2 | null | 1

null หมายถึงไม่มีที่ให้ไปต่อนะครับขั้นแรกเริ่มจาก state เริ่มต้นก่อน พบว่าอักษร a พาไป state 1 ได้ ส่วนอักษร b พาไป state 2 ได้

state  | a | b
{0} | {1} | {2}

แก้ {1} พบว่า a ไปได้ทั้ง 1 หรือ 2 ส่วน b ไปไหนไม่ได้ ในส่วนของ {2} ไป {1} ได้ ถ้าเป็นอักษร b เข้ามา

state  | a | b
{0} | {1} | {2}
{1} | {1, 2} | null
{2} | null | {1}

เราได้ตารางสำหรับ FA มาแล้ว สำหรับ state ปลายทาง

ก็จะเหลือ state {1, 2} ก็ให้ไล่เรียงในแต่ละสมาชิกของ set นี้ ซึ่งก็มีสอง state คือ {1} และ {2} ถ้าอักษรเข้ามาเป็น a แล้วเดินจาก state 1 จะไปได้ทั้งที่ state 1 หรือ state 2 และถ้าเดินจาก state 2 จะไปไหนไม่ได้ รวมแล้วจึงได้ {1, 2}

จากนั้น ไล่ตามอักษรต่อไป ถ้าอักษรเข้ามาเป็น b ถ้าเดินจาก state 1 จะไปไหนไม่ได้ และถ้าเดินจาก state 2 จะไป {1} รวมกันได้ {1}

state | a | b
{0} | {1} | {2}
{1} | {1, 2} | null
{2} | null | {1}
{1, 2} | {1, 2}| {1}

เราก็จะได้ FA สำหรับ NFA ดังกล่าว สำหรับ state ปลายทาง ของ FA (accepting state ที่ FA จะชี้ว่า string ที่เข้ามานั้น ยอมรับได้) คือ set ที่มี state ที่เป็นปลายทางของ NFA กรณีนี้ state 0 และ 1 เป็น accepting state ของ NFA ดังนั้นจาก state ทั้งหมดของ FA จะได้ว่า accepting state ของ FA คือ {0}, {1} และ {1, 2}

อ้างอิง http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/nfa-2-dfa.html

One response to “วิธีแปลง NFA ให้ไปเป็น FA

  1. Pingback: วิธีแปลง NFA-Λ ให้ไปเป็น NFA | Ultimateohm's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s