ตารางการเปลี่ยนสถานะ

ในทฤษฎีออโตมาตาและตรรกศาสตร์เชิงลำดับตารางการเปลี่ยนสถานะคือตารางที่แสดงสถานะ (หรือหลายสถานะในกรณีของออโตมาตาจำกัดแบบไม่กำหนด ) ที่เครื่องสถานะจำกัดจะเปลี่ยนไป โดยพิจารณาจากสถานะปัจจุบันและอินพุตอื่นๆ โดยพื้นฐานแล้วมันคือตารางความจริงที่อินพุตประกอบด้วยสถานะปัจจุบันและอินพุตอื่นๆ ส่วนเอาต์พุตประกอบด้วยสถานะถัดไปและเอาต์พุตอื่นๆ

ตารางการเปลี่ยนสถานะเป็นหนึ่งในหลายวิธีในการระบุเครื่องสถานะจำกัดวิธีอื่นๆ ได้แก่แผนภาพ สถานะ

รูปแบบทั่วไป

มิติเดียว

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

ตารางการเปลี่ยนสถานะ(S: สถานะ, I: ข้อมูลนำเข้า, O: ข้อมูลส่งออก)
ป้อนข้อมูล	สถานะปัจจุบัน	รัฐถัดไป	เอาต์พุต
ฉัน₁	เอส₁	สิ	ออก_ซ์
ฉัน₂	เอส₁	เอส_เจ	โอ้_ย
…	…	…	…
ใน	เอส₁	ส_สก	โอ_ซ
ฉัน₁	เอส₂	S _i′	O _x′
ฉัน₂	เอส₂	S _j′	โอ_วาย'
…	…	…	…
ใน	เอส₂	ส_k′	O _z′
…	…	…	…
ฉัน₁	สม	S _i″	O _x″
ฉัน₂	สม	เอส_เจ″	โอ้_ย"
…	…	…	…
ใน	สม	ส ส_ค″	โอ_ซ″

สองมิติ

ตารางการเปลี่ยนสถานะโดยทั่วไปจะเป็นตารางสองมิติ มีสองวิธีที่นิยมใช้ในการจัดเรียงตารางเหล่านี้

ในวิธีแรก มิติหนึ่งแสดงสถานะปัจจุบัน ในขณะที่อีกมิติหนึ่งแสดงข้อมูลนำเข้า จุดตัดระหว่างแถวและคอลัมน์แสดงสถานะถัดไป และ (อาจมี) ข้อมูลส่งออกที่เกี่ยวข้องกับการเปลี่ยนสถานะ

ตารางการเปลี่ยนสถานะ(S: สถานะ, I: ข้อมูลนำเข้า, O: ข้อมูลส่งออก)
ป้อนข้อมูล สถานะปัจจุบัน	ฉัน₁	ฉัน₂	…	ใน
เอส₁	S _i /O _x	S _j /O _y	…	ส_k /โอ_z
เอส₂	S _i′ /O _x′	S _j′ /O _y′	…	S _k′ /O _z′
…	…	…	…	…
สม	S _i″ /O _x″	S _j″ /O _z″	…	S _k″ /O _z″

ในวิธีที่สอง มิติหนึ่งแสดงสถานะปัจจุบัน ในขณะที่อีกมิติหนึ่งแสดงสถานะถัดไป จุดตัดระหว่างแถวและคอลัมน์แสดงถึงอินพุตและ (อาจมี) เอาต์พุตที่เกี่ยวข้องกับการเปลี่ยนสถานะ

ตารางการเปลี่ยนสถานะ(S: สถานะ, I: ข้อมูลนำเข้า, O: ข้อมูลส่งออก, —: ผิดกฎหมาย)
รัฐถัดไป สถานะปัจจุบัน	เอส₁	เอส₂	…	สม
เอส₁	ฉัน_i /O _x	—	…	—
เอส₂	—	—	…	ฉัน_j /O _y
…	…	…	…	…
สม	—	ฉัน_k /O _z	…	—

รูปแบบอื่นๆ

การเปลี่ยนสถานะพร้อมกันในเครื่องสถานะจำกัดหลายเครื่องสามารถแสดงได้ใน รูปแบบตารางการเปลี่ยนสถานะ nมิติ ซึ่งคู่ของแถวจะแมป (ชุดของ) สถานะปัจจุบันไปยังสถานะถัดไป^{[ 1 ]}นี่เป็นทางเลือกในการแสดงการสื่อสารระหว่างเครื่องสถานะจำกัดที่แยกจากกันและพึ่งพาซึ่งกันและกัน

ในอีกขั้วหนึ่ง มีการใช้ตารางแยกกันสำหรับแต่ละการเปลี่ยนสถานะภายในเครื่องสถานะจำกัดเดียว: "ตาราง AND/OR" ^{[ 2 ]}คล้ายกับตารางการตัดสินใจ ที่ไม่สมบูรณ์ ซึ่งการตัดสินใจสำหรับกฎที่มีอยู่คือการเปิดใช้งานการเปลี่ยนสถานะที่เกี่ยวข้องโดยปริยาย

ตัวอย่าง

ตัวอย่างตารางการเปลี่ยนสถานะพร้อมแผนภาพสถานะ ที่สอดคล้องกัน สำหรับเครื่องสถานะจำกัดที่ยอมรับสตริงที่มีเลข 0 เป็นเลขคู่ แสดงอยู่ด้านล่าง:

ตารางการเปลี่ยนสถานะ
ป้อนข้อมูล สถานะปัจจุบัน	0	1
เอส₁	เอส₂	เอส₁
เอส₂	เอส₁	เอส₂

**แผนภาพสถานะ**

ในตารางการเปลี่ยนสถานะ ค่าป้อนเข้าที่เป็นไปได้ทั้งหมดของเครื่องสถานะจำกัดจะถูกระบุไว้ในคอลัมน์ของตาราง ในขณะที่สถานะที่เป็นไปได้ทั้งหมดจะถูกระบุไว้ในแถว หากเครื่องอยู่ในสถานะ S1 ₍แถวแรก) และได้รับค่าป้อนเข้า 1 (คอลัมน์ที่สอง) เครื่องจะยังคงอยู่ในสถานะ S1 _ต่อไป หากเครื่องอยู่ในสถานะ S1 _และได้รับค่าป้อนเข้า 0 (คอลัมน์แรก) เครื่องจะเปลี่ยนไปสู่สถานะ S2 _ใน แผนภาพสถานะ การเปลี่ยนสถานะแบบแรกจะแสดงด้วยลูกศรวนจาก S1 _ไปยัง S1 _ที่ มีหมายเลข 1 กำกับ และการ เปลี่ยนสถานะแบบหลังจะแสดงด้วยลูกศรจาก S1 _ไปยัง S2 _ที่มีหมายเลข 0 กำกับ กระบวนการนี้สามารถอธิบายได้ทางสถิติโดยใช้ห่วงโซ่มาร์คอฟ

สำหรับเครื่องสถานะจำกัดแบบไม่กำหนด (nondeterministic finite-state machine ) อินพุตอาจทำให้เครื่องอยู่ในสถานะมากกว่าหนึ่งสถานะ ดังนั้นจึง เรียกว่า ไม่กำหนด (non-determinism ) ซึ่งแสดงไว้ในตารางการเปลี่ยนสถานะโดยใช้เครื่องหมายวงเล็บปีกกาคู่ {} ตัวอย่างของตารางการเปลี่ยนสถานะพร้อมแผนภาพสถานะที่สอดคล้องกันสำหรับเครื่องสถานะจำกัดแบบไม่กำหนดแสดงไว้ด้านล่าง:

ตารางการเปลี่ยนสถานะ
ป้อนข้อมูล สถานะปัจจุบัน	0	1
เอส₁	เอส₂	เอส₁
เอส₂	{S ₁ , S ₂ }	เอส₂

**แผนภาพสถานะ**

ถ้าเครื่องอยู่ในสถานะ S2 _และ รับอินพุตเป็น 0 เครื่องจะ อยู่ ในสองสถานะพร้อมกัน คือสถานะ_S1และ_S2

การแปลงจาก/ไปยังแผนภาพสถานะ

สามารถสร้างแผนภาพสถานะจากตารางการเปลี่ยนสถานะได้ โดยมีขั้นตอนง่ายๆ ดังนี้:

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

ดูเพิ่มเติม

อ่านเพิ่มเติม

ไมเคิล ซิปเซอร์: บทนำสู่ทฤษฎีการคำนวณสำนักพิมพ์ PWS บอสตัน 1997 ISBN 0-534-94728-X

[ 1 ]

[ 2 ]