ระบบจะสามารถรับ 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 ไฟล์:Finite50.jpg จากรูป (a) top symbol คือ C จากลำดับของ symbol ทำให้เราทราบว่า 1. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวแรก 2. B คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 2 3. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 3 4. C คือ symbol ที่ถูก PUSH ลงไปเป็นตัวสุดท้าย ไฟล์:Finite60.jpg จากรูป (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 ก็ต่อเมื่อมีการหยุดการทำงาน --Iamion | พูดคุย - 21:01, 27 ตุลาคม 2007 (ICT)
# หัวข้อ
**ตัวหนา**
*ตัวเอียง*
[ลิงก์](url)
- รายการ
> อ้างอิง
ระบบจะสามารถรับ 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 ไฟล์:Finite50.jpg จากรูป (a) top symbol คือ C จากลำดับของ symbol ทำให้เราทราบว่า 1. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวแรก 2. B คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 2 3. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 3 4. C คือ symbol ที่ถูก PUSH ลงไปเป็นตัวสุดท้าย ไฟล์:Finite60.jpg จากรูป (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 ก็ต่อเมื่อมีการหยุดการทำงาน --Iamion | พูดคุย - 21:01, 27 ตุลาคม 2007 (ICT)