Finite State Machines
จากวิกิพีเดีย สารานุกรมเสรี
 |
ส่วนใดส่วนหนึ่งหรือในหลายส่วนด้วยกัน คุณสามารถช่วยตรวจสอบ และแก้ไขบทความนี้ได้ด้วยการกดที่ปุ่ม แก้ไข ด้านบน กรุณาเปลี่ยนไปใช้ป้ายข้อความอื่น เพื่อระบุสิ่งที่ต้องการตรวจสอบ หรือแก้ไข ดูรายละเอียดเพิ่มเติมที่ วิธีแก้ไขหน้าพื้นฐาน คู่มือการเขียน และ นโยบายวิกิพีเดีย ซึ่งสามารถดูตัวอย่างบทความได้ที่ บทความคุณภาพ และเมื่อแก้ไขตามนโยบายแล้ว สามารถนำป้ายนี้ออกได้ |
ระบบจะสามารถรับ input ได้ อาจจะให้ output tและมีmemory ที่สามารถเก็บ input ได้ ในเวลาหนึ่ง ๆ จะมีสถานะ (state) ต่าง ๆ สถานะนี้สามารถบอกได้ถึง Input ที่เข้ามาแล้ว และสถานะ ที่จะเกิดขึ้น เมื่อมี input ใหม่เข้ามาแล้วสถานะ ขึ้นอยู่กับสถานะปัจจุบันและ input ถ้าจำนวนของสถานะมีจำกัด/ นับได้หรือกำหนดได้ Finite-state machine สามารถทำการคำนวณภายในเนื้อที่ในหน่วยความจำที่จำกัดได้ ทำให้มันไม่สามารถที่จะทำงานหลายอย่างภายใต้ข้อจำกัดของคอมไพเลอร์ได้ ดังนั้นจึงต้องมีการสร้างเครื่องมือที่สามารถรองรับการทำงานที่มีลักษณะที่ซับซ้อนมากขึ้น
การสร้างเครื่องมือนี้ต้องอาศัยกลไกการเพิ่มเนื้อที่การทำงาน มีวิธีหนึ่งที่ใช้บ่อยในคอมไพเลอร์ เรียกว่า "Stacking"
Push คือ การเพิ่มข้อมูลเข้าไปใน stack
Pop คือ การย้ายข้อมูลออกจาก stack
Top of stack คือ ข้อมูลที่อยู่บนสุดของ stack
เรียกว่า bottom marker ซึ่งเป็นตัวที่ใช้บอกถึง bottom of stack และไม่สามารถ pop ออกมาได้
ตัวอย่าง 1
จากรูป (a) top symbol คือ C
จากลำดับของ symbol ทำให้เราทราบว่า
1. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวแรก
2. B คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 2
3. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 3
4. C คือ symbol ที่ถูก PUSH ลงไปเป็นตัวสุดท้าย
จากรูป (c) แสดงการ POP symbol C ทำให้ A กลายเป็น top of symbol ซึ่งจะสังเกตเห็นว่าการกระทำกับข้อมูลบน stack นั้น จะทำได้กับข้อมูลที่อยู่บนสุดเท่านั้น
ประโยชน์ของ Finite State Machine
1.ใช้เขียน Model ง่าย ๆ จนถึงการทำที่ยากและซับซ้อน
2.ใช้ในการศึกษา “ Formal Language“
3.ใช้ในการศึกษา Compiler, Programming Language เป็นต้น
Finite and Pushdown
Finite state machine ได้แบ่งการทำงานออกเป็น step ย่อย ในแต่ละ step อาจเปลี่ยนลักษณะใน memory ได้โดยที่เปลี่ยน state และเปลี่ยนการ POP หรือ PUSH STACK
Pushdown machine จะมีขั้นตอนหลายขั้นตอนในการ process แต่ละ symbol ของ input sequence แต่ละขั้นตอนจะถูกควบคุมโดยตัว control ซึ่งเครื่องสามารถที่จะรู้ได้ว่าการ process ของ input sequence นั้นเสร็จสิ้นเมื่อใด
Transition ประกอบด้วย 3 ส่วน
มีดังนี้
1. Stack operation
PUSH ข้อมูลที่ต้องการจัดเก็บลง stack
POP ข้อมูลออกจาก top ของ stack (การ POP stack สามารถทำได้กับข้อมูลตัวบนสุด หรือตัวล่าสุดได้เท่านั้น)
คงสภาพของ stack ไว้เหมือนเดิม ไม่มีการเปลี่ยนแปลง
2. State operation คือ เปลี่ยนจากสถานะหนึ่งไปอีกสถานะหนึ่ง
3. Input operation
รับ input ตัวถัดไปเข้ามาเป็นตัวปัจจุบัน (current) นั่นหมายความว่า "Advance"
ไม่เปลี่ยนแปลง Input นั่นหมายความว่า "Retain"
Pushdown Machine จะถูกระบุโดยสิ่งต่างๆ ดังนี้
1) เชตจำกัดของ Input Symbol ซึ่งจะรวมถึง End Marker ด้วย
2) เชตจำกัดของ Stack Symbol ซึ่งจะรวมถึง Bottom Marker ด้วย
3) เชตจำกัดของ State ซึ่งจะรวมถึงสถานะเริ่มต้น (Starting State) ด้วย
4) สิ่งควบคุม (A Control) ซึ่งจะสั่งให้ทำการ Exit หรือ Transition โดยตัวกระทำจะถูกดึงไปใช้กับ Input จนกระทั่งพบ End Marker หรือทำการ Pop , Push จนพบ End Marker
5) Stack เริ่มต้น ซึ่งจะอยู่ในลักษณะ "Top Symbol On the Right" คือ Bottom Marker จะอยู่ทางซ้ายมือเรียงมาก่อน ตามด้วย Stack Symbol
Pushdown Recognizer
Pushdown Machine จะถูกเรียกว่า Pushdown Recognizer ก็ต่อเมื่อมีการหยุดการทำงาน
--By นางสาวสุพัตรา ปินะถา 48210751 S05 กลุ่ม 17
