State Machine

State Machine กบปญหาลาดบแตมจากการทอยเตา ศล ผเลนสองคน ฌาณกบโนต มลกเตาคนละลก แตละคนทอยเตาของตวเองและจดแตมท! ออกแตละคร#งเป%นล&าดบท!ตอเน'!องกนไป ถาในล&าดบของฌาณปรากฏเลข “12” เขาจะ หย2ดทนทและนบจ&านวนคร#งท#งหมดท!ทอย สวนโนตจะหย2ดทอยเม'อ ! มเลข “11” เก4ดข5#น ในล&าดบ ค2ณผอานค4ดวาจ&านวนคร#งท!ทอยระหวางฌาณกบโนตใครจะมากนอยกวากน ครบ? หร'อเทากน? ป7ญหาขอน#เป%นป7ญหาท!ผเขยนน&าไปต#งกระทเลนกบเพ'อ ! น ๆ ในเว;บบอร<ดของ pantip.com หองหวากอ เพราะค4ดวามแงม2มท! นาสนใจ และเม'!อผเขยนเฉลยป7ญหาดวยเทคน4คการน&า State Machine มาใชค&านวณคาคาดหมายของจ&านวนคร#งท!แตละคน จะตองทอย พบวาเทคน4คน#ชวยลดทอนความซบซอนของการค&านวณและสรางม2มมองอกม2มหน5!งไดอยางสวยงาม จ5งเป%นท!มา ของบทความตอนน# ผเขยนจะน&าเสนอ State Machine และการใช State Machine ชวยแกป7ญหาโจทย<

State Machine ตวอยางยอดน4ยมในการอธ4บายเร'!องน#ค'อตขายส4นคาอตโนมต4 สมมต4วาเราก&าลงพดถ5งตขายชากาแฟชน4ดหยอดเหรยญ ผซ'อ # สามารถเล'อกไดวาตองการเคร'อ ! งด'!มรอนหร'อเย;น เต4มนมหร'อไม เต4มนม หวานหร'อไมหวาน เม'!อผซ'อ # หยอดเหรยญตามราคาส4นคาแลวกดป2Pมเล'อกส4นคา ซ5!งค2ณ อาจจะกดป2Pม ชา/รอน/ไมเต4มนม/หวาน จากน#นก;รอรบถวยกระดาษท!บรรจ2ชารอน เราสามารถ วาดภาพกลไกอยางงายภายในตไดวาประกอบดวย ทอกาแฟ ทอน#&าชา ทอนม ทอน#&าเช'!อม และ ทอน#&าแข;ง โดยทอเหลาน#จะเปTดปTดตามค&าส!งท!ไดรบจากป2Pมกด เชน ถาค2ณกดป2ม P กาแฟ ทอ กาแฟก;จะเปTด, กดป2Pมหวาน ทอน#&าเช'!อมเปTด หร'อกดป2Pมเย;น ทอน#&าแข;งเปTด กลไกดงกลาวแสดง ภาพอยางงายของแบบจ&าลอง (model) ท!ประกอบดวย ขอมลปZอนเขา (input), ผลลพธ< (output) และกระบวนการ (process) ขอมลท!ปZอนเขาไดแกป2Pมกด จากตวอยางเราอาจจะมเพยง 5 ป2Pม ชา (T), กาแฟ (C), เต4มน#&าแข;ง (I), เต4มนม (M), เต4มน#&าเช'!อม (S) (วาโดยหลกการการ ออกแบบท!ดแลว ชากบกาแฟควรใชป2Pมเดยวกน โดยอาจจะ ก&าหนด “กด” หมายถ5งชา และ “ไมกด” หมายถ5งกาแฟ) สวน กระบวนการจะดวา input ค'ออะไร แลวด&าเน4นการตาม input เชน เปTดทอน#น ปTดทอน# ผลท!ไดจากกระบวนการเราเรยกวา output ซ5!งแบบจ&าลองดงกลาวสามารถเขยนในรปสมการ อธ4บายความสมพนธ<อยางงายได Z = f(T, C, I, M, S) เม'อ ! Z ค'อ output และ Z ε {ชานมรอนหวาน, ชานมรอนจ'ด, ชานม เย;นหวาน, ชานมเย;นจ'ด, ชารอนหวาน, ชารอนจ'ด, ชาเย;นหวาน, ชาเย;นจ'ด, กาแฟนมรอน หวาน, กาแฟนมรอนจ'ด, กาแฟนมเย;นหวาน, กาแฟนมเย;นจ'ด, กาแฟด&ารอนหวาน, กาแฟด&า รอนจ'ด, กาแฟด&าเย;นหวาน, กาแฟด&าเย;นจ'ด} ถาก&าหนดให “1” = กดป2Pม และ “0” = ไมกด ป2Pม จากโมเดล Z = f(T, C, I, M, S) จะพบวา f(1, 0, 1, 1, 1) ค'อ ชานมเย;นหวาน เราเรยก วงจร (หร'อกลไก) ท!สรางจากโมเดลท!มความสมพนธ< “output = f(input)” แบบน#วาวงจร combination นอกจากวงจร combination ยงมวงจรท!เป%นสวนส&าคญอยางย4!งอกสวนหน5!งใน ตขายส4นคาอตโนมต4 น!นค'อวงจร sequential ซ5!งวงจรน#แหละครบ สรางจากโมเดลท!เรยกวา “State Machine” สมมต4วาคากาแฟหร'อชารอน 5 บาท ถาเต4มนมตองเพ4!มเง4นอก 5 บาท ใสน#&าเช'อ ! มเพ4!มเง4นอก 5 บาท ใสน#&าแข;งก;เพ4!มเง4นอก 5 บาท และตขายเคร'อ ! งด'ม ! ตน#รบเฉพาะเหรยญ 5 บาทเทาน#น ถาค2ณตองการกาแฟนมเย;นหวาน ค2ณจะตองเตรยมเหรยญ 5 บาท 4 เหรยญใหพรอมกอนท!จะไปย'นหนาต กรอบความสนใจของเราอยท!ระบบนบเง4นนะครบ เหรยญท!หยอดลงตจะผานวงจรตรวจ จบเหรยญหาบาท ถามเหรยญหาไหลผาน วงจรจะสงขอความบอกวา “ใชเหรยญหา” (Got 5 Baht = 1) แตถาเหรยญท!ผาน ไมใชเหรยญหา วงจรก;จะสงขอความบอกวา “ไมใชเหรยญหา” (Got 5 Baht = 0) ซ5!งขอความสองขอความน#จะเป%น input ให กบระบบนบเง4น สวน output ของระบบนบเง4นก;คอ ' การย4นยอมใหกดป2Pม สมมต4วาค2ณหยอดเง4นแค 10 บาท ตขายเคร'อ ! งด'ม ! ก;จะ ย4นยอมใหค2ณกดป2Pมเพยง 2 ป2Pม ค'อ ป2Pม T หร'อ C (เพ'อ ! เล'อกชาหร'อกาแฟ) และป2Pมใดอกป2Pมหน5!งในกล2ม I, M, S (ถาอยากกด มากกวาน#กต ; องจายมากกวาน#) ถาเราจะเขยนสมการความสมพนธ<ของระบบนบเง4นโดยเลยนแบบโมเดลของวงจร combination เราจะได Z = f(Got 5 Baht) และ Z ε {กดได 0 ป2Pม, กดได 1 ป2Pม, กดได 2 ป2Pม, กดได 3 ป2Pม, กดได 4 ป2Pม} คง เห;นไดไมยากวา input เพยงตวเดยวและเป%น input ท!มเพยงสองสถานะ (digital input) ค'อ 1 (ใชเหรยญหา) และ 0 (ไมใช เหรยญหา) เพยงแคน#ไมสามารถใชก&าหนด output ท!มถ5ง 5 สถานะได ในความเป%นจร4ง เม'!อเราหยอดเหรยญหาบาทเหรยญ แรกลงไปแลว ตจะยอมใหเรากดได 1 ป2Pม และเม'!อเราหยอดเหรยญหาบาทเหรยญท!สอง ตจะยอมใหเรากดอก 1 ป2Pม และเม'อ ! เราหยอดเหรยญหาบาทอกเป%นเหรยญท!สาม ตก;จะยอมใหเรากดเพ4ม ! อก 1 ป2Pม สงเกตตรงน#ใหดนะครบ input ของการหยอด

เหรยญแตละเหรยญเหม'อนเด4ม ค'อ “1” แต output ของการหยอดเหรยญแตละคร#งไมเหม'อนกน ค'อ “กดได 1 ป2Pม”, “กดได 2 ป2Pม” และ “กดได 3 ป2Pม” ตามล&าดบ น!นหมายความวา output ไมไดข5#นอยกบ input เพยงอยางเดยว แตมนข5#นอยกบสถานะ (state) ของมนขณะน#นดวย อาจเขยนความสมพนธ<รปท!วไปอยางงาย “output = f(input, state)” ค&าวา “สถานะ” ในตวอยาง น#หมายถ5งจ&านวนเง4นสะสมท!หยอดต ดงน#นสถานะท#งหมดท!เป%นไปไดค'อ {มเง4น 0 บาท, มเง4น 5 บาท, มเง4น 10 บาท, มเง4น 15 บาท, มเง4น ≥ 20 บาท} โมเดลท!เขยนความสมพนธ<ในรป “output = f(input, state)” ค'อ State Machine และวงจร ( หร'อกลไก) ท!สรางจากโมเดลน#เรยกวาวงจร sequential จากตวอยางระบบนบเง4นเราสามารถเขยน Z = f(Got 5 Baht, state) เชน f(1, มเง4น 15 บาท) ค2ณก;สามารถกดป2Pมได 3 ป2Pม (เล'อกชาหร'อกาแฟ 1 ป2Pม และเล'อกกด I, M, S ไดอก 2 ป2Pม) เปรยบเทยบระหวางวงจร combination หร'อโมเดล output = f(input) กบวงจร sequential หร'อโมเดล output = f(input, state) ไดดงแผนภาพ

f

input

output = f(input)

f

input

output = f(input, state)

state

วงจร combination

วงจร sequential

ว4ธท!มประส4ทธ4ภาพว4ธหน5!งในการบรรยาย State Machine1 ค'อการเขยนแผนภาพ State หร'อ State Diagram2 วากนตามตรง การแกป7ญหาโจทย<ล&าดบแตมลกเตาขอน# ผอานไมจ&าเป%นตองรจก State Machine ก;สามารถเรยนรท!จะวาด State diagram ได แตผเขยนมความเช'!อวาถาเราเห;นภาพรวมของ State Machine ในม2มกวาง ก;นาจะมประโยชน<และชวยใหเก4ดความกระจาง ในการก&าหนด state มากย4!งข5#น การวาด state diagram ส4!งท!จ&าเป%นตองรค'อ state ท#งหมด, input, output และป7จจยท!ท&าให เก4ดการเปล!ยน state สญลกษณ<ท!วไปก&าหนดใหวงกลมแทน state แตละ state และท4ศทางของลกศรแสดงการเปล!ยน state จาก state ปลายลกศรไปส state หวลกศร บนเสนลกศรจะเขยน input/output ก&ากบ แผนภาพตอไปน#แสดง state diagram ของระบบนบเง4นท!ม input ค'อ {ใชเหรยญหาบาท (1), ไมใชเหรยญหาบาท (0)}, output ค'อ {กดได 0 ป2Pม, กดได 1 ป2Pม, กด ได 2 ป2Pม, กดได 3 ป2Pม, กดได 4 ป2Pม} และ state ท#งหมด ไดแก {มเง4น 0 บาท, มเง4น 5 บาท, มเง4น 10 บาท, มเง4น 15 บาท, มเง4น ≥ 20 บาท} 0/กดได 3 ป2ม P 0/กดได 0 ป2ม P

มเง4น 0 บาท

1/กดได 1 ป2ม P

0/กดได 1 ป2ม P

มเง4น 5 บาท

1/กดได 2 ป2ม P

0/กดได 2 ป2ม P

มเง4น 10 บาท

1/กดได 3 ป2ม P

0/กดได 4 ป2ม P

มเง4น 15 บาท

1/กดได 4 ป2ม P

มเง4น ≥ 20 บาท

ตอไปผเขยนจะท&าให State Machine ซบซอนข5#นกวาเด4มโดยการอพเกรดตน#ใหสามารถรบเหรยญ 10 บาทเพ4ม ! ข5#นอกหน5!ง เหรยญ ฉะน#น input จะเพ4!มข5#นจากเด4ม ค'อ 0 = ไมใชเหรยญหาบาท, 1 = ใชเหรยญหาบาท เป%น 0 = ไมใชเหรยญหาหร'อ ไมใชเหรยญส4บบาท, 1 = ใชเหรยญหาบาท, 2 = ใชเหรยญส4บบาท State Machine ท!มจ&านวน state จ&ากด มช'!อเรยกวา Finite State Machine (FSM) ถาหากค2ณผอานมโอกาสไดคนควาตอ ในว4ชา Digital Circuit ค2ณผอานจะพบวา FSM ม 2 ชน4ดไดแก Moore และ Mealy ซ5!งท#งคแตกตางกนท!การสราง output ส&าหรบ Moore คา output = f(state) สวน Mealy คา output = f(input, state) ถาค2ณผอานเห;น output = f(state) ก;ไม ตองแปลกใจวา input หายไปไหนนะครบ เพราะไมวาอยางไร state ก;ข5#นอยกบ input น!นแหละ ส&าหรบ diagram ท!ผเขยน วาดในบทความน#ย5ดตามแบบ Mealy 1

2

State Diagram เม'!อพดโดยรวม state diagram เป%น diagram ท!ใชบรรยายพฤต4กรรมของระบบ ซ5ง! เจอบอยในว4ชาสาขา Computer Science และ Digital Electronics บ2คคลแรกท!บรรยาย FSM ดวย state diagram ค'อ Taylor Booth (จากหนงส'อ Sequential Machines and Automata Theory) นกคณ4ตศาสตร<ผมผลงานโดดเดนในทฤษฎ automata

2/กดได 3 ป2Pม

มเง4น 0 บาท

1/กดได 1 ป2ม P

0/กดได 2 ป2ม P

0/กดได 1 ป2ม P

0/กดได 0 ป2ม P

มเง4น 5 บาท

0/กดได 3 ป2ม P

1/กดได 2 ป2ม P

มเง4น 10 บาท

2/กดได 2 ป2Pม

0/กดได 4 ป2ม P

มเง4น 15 บาท

1/กดได 3 ป2ม P

1, 2/กดได 4 ป2ม P

มเง4น ≥ 20 บาท

2/กดได 4 ป2Pม

ปญหาลาดบแตมจากการทอยเตา กลบไปท!ผเลนเกม ฌาณกบโนต ถาดเพยงผ4วเผ4นเหม'อนกบโจทย<ถามเราวาโอกาสเก4ด “12” กบโอกาสเก4ด “11” เทากนหร'อ ไม? อยาหลงกลโจทย<แลวรบตอบวาเทากนนะครบ แนนอนวาโอกาสเก4ด “1” ตวแรกของฌาณกบโนตเทากน ระยะเวลาท!รอให ออกแตม 1 (หร'อจ&านวนทท!รอ) ก;ควรท!จะเทากน สมมต4วาท#งคได 1 ตวแรกมาครอบครองกนแลว ตอนน#โนตก&าลงรอ “1” ตวท! สอง ซ5!งมโอกาสเก4ดข5#นเทากบ 1/6 และฌาณก;รอ “2” มโอกาสเก4ดข5#นเทากบ 1/6 เทากน ส&าหรบท#งค โอกาสไมออก 1 ก; เทากบโอกาสท!ไมออก 2 ค'อ 5/6 ถาในการทอยคร#งน# โนตไมได “1” เขาจะตองเร4!มตนรอ “1” ตวแรกใหม ในขณะท!ฌาน ถ5ง แมวาในการทอยคร#งน#จะไมได “2” แตถาฌาณได “1” เขาก;ยงสามารถคงสถานะรอ “2” เอาไวเหม'อนเด4มได จ2ดน#เป%นขอได เปรยบของฌานท!ท&าใหเราสามารถสร2ปไดวา ฌาณจะใชจ&านวนคร#งท!ทอยนอยกวาโนต ไดเวลาค&านวณตวเลขออกมากนแลวครบ ระหวางจ&านวนคร#งท!ทอยของฌาณกบโนต ใครจะไดเทาไร? และมากนอยกวากน เทาไร? เร4!มจากเขยน state diagram ส&าหรบกลไกการรอ “11” ของโนต input ค'อแตมท!ออกจากการทอยเตา {1, 2, 3, 4, 5, 6}, output ม 2 สถานะค'อ {เลนตอ, จบเกม} และม 3 states {รอ “1” ตวท! 1, รอ “1” ตวท! 2, หย2ด} 1/ เลนตอ ไมใช 1/ เลนตอ S1 =

S0=

รอ “1” ตวท! 2

รอ “1”

ตวท! 1

1/ จบเกม

S2 =หย2ด

ไมใช 1/ เลนตอ ถาก&าหนดใหท! state เร4!มตน (S0) โนตจะตองทอยเตา W คร#งจ5งจะไดล&าดบ “11” (S2) และโอกาสท!ทอยเตาได 1 เทากบ p = 1/6 เราสามารถเขยนความสมพนธ< W = (1-p)(W+1) + (p)[(1-p)(W+2) + 2p] อธ4บายสมการ: มทางออกจาก S0 สองทาง ทางแรกค'อกลบมายง S0 ท!เด4ม มโอกาส 1-p และในเม'!อมนยงอยท! S0 ณ จ2ดน#จ5ง ใชเวลารอเทาเด4ม (W) จนกวาจะจบเกม (อยาล'มวาค2ณตองทอยเตาแลว 1 คร#งจ5งกลบมาท!จด 2 น#ไดนะครบ) อกทางค'อไปตอยง S1 มโอกาส p และท! S1 มโอกาส 1-p จะกลบไปท! S0 (ถากลบไปรอบน#แปลวาทอยเตามาแลว 2 คร#ง) และมโอกาส p ท!จะถ5ง S2 (เราทอยเตา 2 คร#ง) เน'!องจากเป%นสมการตวแปรเดยว สามารถแกสมการได W = (1+p)/p2 = 42 ดงน#นคาคาดหมายจ&านวนคร#งท!ทอยเตาของโนต เทากบ 42 คร#ง ท&านองเดยวกน วาด state diagram ของฌานไดดงรป

1/ เลนตอ

1/ เลนตอ

ไมใช 1/ เลนตอ S0=

รอ “1”

S1 =

รอ “2”

2/ จบเกม

S2 =หย2ด

ไมใช 1 และไมใช 2/ เลนตอ ก&าหนดให W0 แทนคาคาดหมายของจ&านวนคร#งท!ทอยเตาเม'อ ! อย S0 กระท!งไดล&าดบ “12” (หร'อถ5ง S2), W1 แทนคาคาดหมาย จ&านวนคร#งท!ทอยเตาเม'!ออย S1 จนถ5ง S2 และ p แทนโอกาสทอยเตาไดแตม 1 W0 = (1-p)(W0+1) + (p)(W1+1) W1 = (p)(W1+1) + (1-2p)(W0+1) + (p)(1) แกระบบสมการหาคา W0 = 36 ดงน#นคาคาดหมายจ&านวนคร#งท!ทอยเตาของฌาณเทากบ 36 คร#ง นอยกวาโนตถ5ง 6 คร#ง เป%น ไงบางครบ ค2ณผอานค4ดวาโจทย<ลกษณะน# ใช state diagram ชวยใหเราเห;นภาพไดชดเจนย4!งข5#นและสามารถว4เคราะห<ความ สมพนธ<ไดงายข5#นบางม#ยครบ?