Moore และ Mealy Machines
Finite automata อาจมีเอาต์พุตที่สอดคล้องกับการเปลี่ยนแต่ละครั้ง มีเครื่องจักรสถานะ จำกัด สองประเภทที่สร้างเอาต์พุต -
- เครื่องแป้ง
- เครื่องมัวร์
เครื่องแป้ง
Mealy Machine เป็น FSM ซึ่งเอาต์พุตขึ้นอยู่กับสถานะปัจจุบันและอินพุตปัจจุบัน
สามารถอธิบายได้ด้วย 6 ทูเปิล (Q, ∑, O, δ, X, q 0 ) โดยที่ -
Q เป็นชุดของรัฐที่ จำกัด
∑ เป็นชุดสัญลักษณ์ จำกัด ที่เรียกว่าตัวอักษรอินพุต
O เป็นชุดสัญลักษณ์ จำกัด ที่เรียกว่าอักษรเอาต์พุต
δ คือฟังก์ชั่นการเปลี่ยนอินพุตโดยที่δ: Q × ∑ → Q
X คือฟังก์ชันการเปลี่ยนเอาต์พุตโดยที่ X: Q × ∑ → O
q0คือสถานะเริ่มต้นจากการประมวลผลอินพุตใด ๆ (q 0 ∈ Q)
ตารางสถานะของเครื่อง Mealy แสดงไว้ด้านล่าง -
| สถานะปัจจุบัน | ชาติหน้า | |||
|---|---|---|---|---|
| อินพุต = 0 | อินพุต = 1 | |||
| สถานะ | เอาต์พุต | สถานะ | เอาต์พุต | |
| →ก | ข | x 1 | ค | x 1 |
| ข | ข | x 2 | ง | x 3 |
| ค | ง | x 3 | ค | x 1 |
| ง | ง | x 3 | ง | x 2 |
แผนภาพสถานะของ Mealy Machine ข้างต้นคือ -
มัวร์แมชชีน
Moore machine เป็น FSM ที่เอาต์พุตขึ้นอยู่กับสถานะปัจจุบันเท่านั้น
เครื่อง Moore สามารถอธิบายได้ด้วย 6 tuple (Q, ∑, O, δ, X, q 0 ) โดยที่ -
Q เป็นชุดของรัฐที่ จำกัด
∑ เป็นชุดสัญลักษณ์ จำกัด ที่เรียกว่าตัวอักษรอินพุต
O เป็นชุดสัญลักษณ์ จำกัด ที่เรียกว่าอักษรเอาต์พุต
δ คือฟังก์ชั่นการเปลี่ยนอินพุตโดยที่δ: Q × ∑ → Q
X คือฟังก์ชันการเปลี่ยนเอาต์พุตโดยที่ X: Q → O
q0คือสถานะเริ่มต้นจากการประมวลผลอินพุตใด ๆ (q 0 ∈ Q)
ตารางสถานะของ Moore Machine แสดงไว้ด้านล่าง -
| สถานะปัจจุบัน | รัฐถัดไป | เอาต์พุต | |
|---|---|---|---|
| อินพุต = 0 | อินพุต = 1 | ||
| →ก | ข | ค | x 2 |
| ข | ข | ง | x 1 |
| ค | ค | ง | x 2 |
| ง | ง | ง | x 3 |
แผนภาพสถานะของ Moore Machine ข้างต้นคือ -
Mealy Machine กับ Moore Machine
ตารางต่อไปนี้เน้นประเด็นที่ทำให้ Mealy Machine แตกต่างจาก Moore Machine
| เครื่องแป้ง | มัวร์แมชชีน |
|---|---|
| เอาต์พุตขึ้นอยู่กับสถานะปัจจุบันและอินพุตปัจจุบัน | ผลลัพธ์ขึ้นอยู่กับสถานะปัจจุบันเท่านั้น |
| โดยทั่วไปจะมีสถานะน้อยกว่า Moore Machine | โดยทั่วไปจะมีสถานะมากกว่า Mealy Machine |
| ค่าของฟังก์ชันเอาต์พุตเป็นฟังก์ชันของการเปลี่ยนและการเปลี่ยนแปลงเมื่อตรรกะอินพุตในสถานะปัจจุบันเสร็จสิ้น | ค่าของฟังก์ชันเอาต์พุตเป็นฟังก์ชันของสถานะปัจจุบันและการเปลี่ยนแปลงที่ขอบนาฬิกาเมื่อใดก็ตามที่เกิดการเปลี่ยนแปลงสถานะ |
| เครื่องจักร Mealy ตอบสนองต่ออินพุตได้เร็วขึ้น โดยทั่วไปจะตอบสนองในวงจรนาฬิกาเดียวกัน | ในเครื่อง Moore จำเป็นต้องใช้ตรรกะมากขึ้นในการถอดรหัสเอาต์พุตซึ่งส่งผลให้วงจรล่าช้ามากขึ้น โดยทั่วไปจะตอบสนองหนึ่งรอบนาฬิกาในภายหลัง |
Moore Machine ไปยัง Mealy Machine
อัลกอริทึม 4
Input - เครื่องมัวร์
Output - เครื่องแป้ง
Step 1 - ใช้รูปแบบตารางการเปลี่ยนแปลง Mealy Machine ที่ว่างเปล่า
Step 2 - คัดลอกสถานะการเปลี่ยนแปลงของ Moore Machine ทั้งหมดลงในรูปแบบตารางนี้
Step 3- ตรวจสอบสถานะปัจจุบันและผลลัพธ์ที่เกี่ยวข้องในตารางสถานะของ Moore Machine หากเอาต์พุตสถานะ Q iคือ m ให้คัดลอกลงในคอลัมน์เอาต์พุตของตารางสถานะ Mealy Machine ที่ใดก็ตามที่ Q iปรากฏในสถานะถัดไป
ตัวอย่าง
ให้เราพิจารณาเครื่อง Moore ดังต่อไปนี้ -
| สถานะปัจจุบัน | รัฐถัดไป | เอาต์พุต | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| →ก | ง | ข | 1 |
| ข | ก | ง | 0 |
| ค | ค | ค | 0 |
| ง | ข | ก | 1 |
ตอนนี้เราใช้ Algorithm 4 เพื่อแปลงเป็น Mealy Machine
Step 1 & 2 -
| สถานะปัจจุบัน | รัฐถัดไป | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| สถานะ | เอาต์พุต | สถานะ | เอาต์พุต | |
| →ก | ง | ข | ||
| ข | ก | ง | ||
| ค | ค | ค | ||
| ง | ข | ก | ||
Step 3 -
| สถานะปัจจุบัน | รัฐถัดไป | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| สถานะ | เอาต์พุต | สถานะ | เอาต์พุต | |
| => ก | ง | 1 | ข | 0 |
| ข | ก | 1 | ง | 1 |
| ค | ค | 0 | ค | 0 |
| ง | ข | 0 | ก | 1 |
Mealy Machine ไปยัง Moore Machine
อัลกอริทึม 5
Input - เครื่องแป้ง
Output - เครื่องมัวร์
Step 1- คำนวณจำนวนเอาต์พุตที่แตกต่างกันสำหรับแต่ละสถานะ (Q i ) ที่มีอยู่ในตารางสถานะของเครื่อง Mealy
Step 2- ถ้าหากผลของฉีเหมือนกันคัดลอกรัฐ Q ฉัน หากมี n เอาต์พุตที่แตกต่างกันให้แบ่ง Q iเป็น n สถานะเป็น Q ในที่ใดn = 0, 1, 2 .......
Step 3 - หากเอาต์พุตของสถานะเริ่มต้นเป็น 1 ให้ใส่สถานะเริ่มต้นใหม่ที่จุดเริ่มต้นซึ่งให้เอาต์พุต 0
ตัวอย่าง
ให้เราพิจารณา Mealy Machine ต่อไปนี้ -
| สถานะปัจจุบัน | รัฐถัดไป | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| รัฐถัดไป | เอาต์พุต | รัฐถัดไป | เอาต์พุต | |
| →ก | ง | 0 | ข | 1 |
| ข | ก | 1 | ง | 0 |
| ค | ค | 1 | ค | 0 |
| ง | ข | 0 | ก | 1 |
ที่นี่สถานะ 'a' และ 'd' ให้ผลลัพธ์เพียง 1 และ 0 ตามลำดับดังนั้นเราจึงคงสถานะ 'a' และ 'd' แต่สถานะ 'b' และ 'c' ให้ผลลัพธ์ที่แตกต่างกัน (1 และ 0) ดังนั้นเราจึงแบ่งb เป็น b0, b1 และ c เป็น c0, c1.
| สถานะปัจจุบัน | รัฐถัดไป | เอาต์พุต | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| →ก | ง | ข1 | 1 |
| ข0 | ก | ง | 0 |
| ข1 | ก | ง | 1 |
| ค0 | ค1 | ค0 | 0 |
| ค1 | ค1 | ค0 | 1 |
| ง | ข0 | ก | 0 |