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

ต่อจากตอนที่แล้ว ซึ่งถ้าเจอเส้นที่เป็น Λ (บางตำราใช้ตัวอักษร ε แทน) เราต้องหาวิธีแปลงให้ NFA-Λ ให้ไม่มี Λ ไปเป็น NFA ที่ใช้วิเคราะห์ string เดียวกันได้

ขอนิยาม Λ(a) หมายถึง closure ที่ input เป็น set a แบบที่มีสมาชิกเป็น state และ output จาก Λ(a) จะเป็น set ของ state ที่สามารถเดินทางไปถึงได้จาก state ที่อยู่ใน a ด้วยเส้น Λ ทั้งนี้ให้ถือว่า state ใน a สามารถเดินทางไปหา a ได้เสมอ (สมาชิกทุกตัวของ a จะเจอใน Λ(a) เสมอ) และต้องมองข้ามช็อตหลายชิ่ง ถ้า state ปลายทางที่ไปถึงด้วย Λ นั้น มีไปต่อด้วย Λ ไปยัง state อื่นๆ ได้อีก ต้องรวม state นั้นๆ เพิ่มเข้าไปด้วย

การแปลงจาก NFA-Λ ไปเป็น NFA นั้นจำนวน state และชื่อ state จะไม่เปลี่ยน วิธีการหาว่า state หนึ่งๆ ใน NFA-Λ นั้น เมื่อได้รับ input แล้วจะไปยัง state ไหนของ NFA บ้าง ขั้นแรกให้เราหา Λ({q}) ของ state q นั้นๆ จากนั้นให้แยกออกไปตาม input ในแต่ละแบบ (ไม่รวม Λ) ว่า จากทุก state ที่ Λ({q}) ตอบค่ากลับมานั้น ไปยัง state ไหนได้บ้าง สมมติให้เป็น set p จะได้ว่าจาก state q เมื่อใส่ input นั้นๆ จะไป state ที่ตอบกลับมาโดย Λ(p)

สำหรับ state เริ่มต้นนั้นไม่เปลี่ยน ส่วน accept state ของ NFA ที่แปลงได้มาจาก NFA-Λ นั้นเหมือนเดิมแต่จะรวม state เริ่มต้นเข้าไปด้วย ถ้า closure ของ state เริ่มต้นนั้นมี accept state ปะปนอยู่ด้วย ขอยกตัวอย่าง ซึ่งทำเป็นตาราง คงเห็นภาพมากกว่า

(ตัวอย่างรอแป๊ปนะครับ)

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

 

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

  1. Pingback: วิธีแปลง NFA ให้ไปเป็น FA | 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