เครื่องจักรสถานะจำกัดและภาษาเรกูลาร์

เครื่องจักรสถานะจำกัดเป็นเครื่องจักรคำนวณที่ง่ายที่สุด โดยอ่านข้อมูลนำเข้าทีละสัญลักษณ์โดยใช้สถานะภายในจำนวนจำกัดเท่านั้น และภาษาที่เครื่องจักรเหล่านี้รู้จักก็คือภาษาเรกูลาร์นั่นเอง

Definition

เครื่องจักรสถานะจำกัดคือเครื่องจักรที่มีชุดสถานะจำกัด, ฟังก์ชันการเปลี่ยนสถานะตามสัญลักษณ์นำเข้า, สถานะเริ่มต้น, และสถานะยอมรับ; เครื่องจักรจะยอมรับสายอักขระหากการอ่านสายอักขระนั้นนำเครื่องจักรจากสถานะเริ่มต้นไปยังสถานะยอมรับ และชุดของสายอักขระที่ยอมรับได้คือภาษาของเครื่องจักรนั้น

Scope

หัวข้อนี้ครอบคลุมถึงเครื่องจักรสถานะจำกัดแบบกำหนดและไม่กำหนด, ความสมมูลกันผ่านการสร้างเซตย่อย, นิพจน์เรกูลาร์และทฤษฎีบทของคลีน, ทฤษฎีบทของ Myhill–Nerode และการลดสถานะให้เหลือน้อยที่สุด, คุณสมบัติการปิดของภาษาเรกูลาร์, และเลมมาการปั๊มที่ใช้ในการพิสูจน์ว่าภาษาบางภาษาไม่ใช่ภาษาเรกูลาร์

Core questions

• ภาษาใดบ้างที่สามารถจดจำได้โดยใช้หน่วยความจำที่จำกัดและคงที่เท่านั้น?
• เหตุใดเครื่องจักรสถานะจำกัดแบบกำหนดและไม่กำหนดจึงมีพลังเท่าเทียมกัน?
• จะพิสูจน์ได้อย่างไรว่าภาษาเฉพาะไม่ใช่ภาษาเรกูลาร์?
• เครื่องจักรสถานะอัตโนมัติที่เล็กที่สุดที่รู้จักภาษาเรกูลาร์ที่กำหนดคืออะไร?

Key theories

การสร้างเซตย่อย

เครื่องจักรสถานะจำกัดแบบไม่กำหนดใดๆ สามารถจำลองได้ด้วยเครื่องจักรสถานะจำกัดแบบกำหนดซึ่งมีสถานะเป็นเซตของสถานะเดิม ซึ่งพิสูจน์ว่าแบบจำลองทั้งสองรู้จักภาษาเดียวกันอย่างแม่นยำ

ทฤษฎีบทของคลีน

ภาษาหนึ่งจะถูกรู้จักโดยเครื่องจักรสถานะจำกัดก็ต่อเมื่อภาษานั้นถูกอธิบายด้วยนิพจน์เรกูลาร์ ซึ่งเป็นการสร้างความสมมูลกันระหว่างคำอธิบายเชิงเครื่องจักรและเชิงพีชคณิตของภาษาเรกูลาร์

ทฤษฎีบทของ Myhill–Nerode

ภาษาหนึ่งจะเป็นภาษาเรกูลาร์ก็ต่อเมื่อความสัมพันธ์ของการแยกแยะสายอักขระ (string indistinguishability) มีคลาสจำกัด และคลาสเหล่านี้กำหนดเครื่องจักรสถานะจำกัดแบบกำหนดที่น้อยที่สุดและไม่ซ้ำกันสำหรับภาษานั้น

Clinical relevance

เครื่องจักรสถานะจำกัดเป็นกลไกเบื้องหลังการจับคู่นิพจน์เรกูลาร์, สแกนเนอร์และตัววิเคราะห์คำศัพท์ในคอมไพเลอร์, การค้นหาและแทนที่ในโปรแกรมแก้ไขข้อความ, และการตรวจจับรูปแบบในระบบตรวจจับการบุกรุกเครือข่าย ซึ่งการจดจำด้วยหน่วยความจำที่จำกัดทำให้การประมวลผลรวดเร็วและคาดการณ์ได้

History

จากแบบจำลองโครงข่ายประสาทของ McCulloch และ Pitts ในปี 1943 คลีนได้อธิบายลักษณะของเหตุการณ์ที่เครื่องจักรสถานะจำกัดสามารถแสดงได้ประมาณปี 1951 และ Rabin กับ Scott ได้กำหนดรูปแบบเครื่องจักรสถานะไม่กำหนดและปัญหาการตัดสินใจของเครื่องจักรเหล่านั้นในปี 1959 ซึ่งเป็นผลงานที่ได้รับการยอมรับในภายหลังด้วยรางวัล Turing Award

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Anil Nerode

Seminal works

• rabinScott1959
• sipser2013

Frequently asked questions

จะแสดงได้อย่างไรว่าภาษาหนึ่งไม่ใช่ภาษาเรกูลาร์?

เครื่องมือที่ใช้บ่อยที่สุดคือเลมมาการปั๊ม ซึ่งกล่าวว่าสายอักขระที่ยาวพอในภาษาเรกูลาร์ทุกสายจะประกอบด้วยสายอักขระย่อยที่สามารถทำซ้ำได้หลายครั้งโดยยังคงอยู่ในภาษา การหาสายอักขระที่ไม่สามารถปั๊มได้ด้วยวิธีนี้พิสูจน์ว่าภาษาดังกล่าวไม่ใช่ภาษาเรกูลาร์; ทฤษฎีบทของ Myhill–Nerode ให้ข้อโต้แย้งทางเลือกโดยการแสดงคำนำหน้า (prefixes) ที่แตกต่างกันได้ไม่จำกัดจำนวน

หากเครื่องจักรสถานะไม่กำหนดไม่ได้มีพลังมากกว่า แล้วทำไมถึงยังใช้?

โดยทั่วไปแล้ว เครื่องจักรเหล่านี้มักจะเล็กกว่ามากและออกแบบได้ง่ายกว่า หรือสามารถสร้างขึ้นจากนิพจน์เรกูลาร์ได้ง่ายกว่า การสร้างเซตย่อยสามารถแปลงเครื่องจักรเหล่านี้ให้อยู่ในรูปแบบกำหนดได้เมื่อจำเป็น โดยอาจมีค่าใช้จ่ายแบบเอ็กซ์โพเนนเชียลในจำนวนสถานะ ดังนั้นการไม่กำหนดจึงเป็นเครื่องมือในการระบุที่สะดวกสบายมากกว่าการเพิ่มพลังในการจดจำ