Please enable JavaScript.
Coggle requires JavaScript to display documents.
ออโตมาตาจํากัดที่มีข้อมูลออก - Coggle Diagram
ออโตมาตาจํากัดที่มีข้อมูลออก
เป็นการศึกษาเครื่อง สถานะจํากัดที่รับข้อมูลเข้าเป็นสตริงและแปลงให้เป็นสตริงผลลัพธ์ มีด้วยกัน 2 ตัว
เครื่องมีลลี (Mealy machine)
จะมีการระบุตัวอักขระที่ต้องการแสดงผลไว้ที่เส้นเชื่อม โหนดแต่ละเส้น
เครื่องมัวร์ (Moore Machine)
จะมีการระบุตัวอักขระที่ต้องการแสดงผลไว้ที่ชื่อโหนด
เครื่องจักรทั้งสองสามารถทํางานได้เหมือนกันในการแก้ปัญหาถ้าปัญหาหนึ่งสามารถใช้ เครื่องจักรชนิดแรกหาคําตอบ แล้วเราสามารถใช้เครื่องจักรอีกชนิดหน่ึง ในการหาคําตอบได้
Moore machine ประกอบด้วย
เซตจํากัดของสถานะ q0, q1, q2, … โดยที่ q0 เป็นสถานะเริ่มต้น
ชุดตัวอักษร Σ ของสตริงรับเข้า เช่น Σ = { a, b, c, … }
ชุดตัวอักษร Γ ของสตริงออก เช่น Γ = { x, y, z, … }
Transition table หมายถึง การเดินทางของสถานะต่อสตริงเข้า
Output table หมายถึง การส่งสตริงออก จาก Γ เมื่อเดินถึงสถานะต่างๆ
ตัวอย่าง
เครื่องมัวร์ในการนับจํานวนของ baa
สตริงเข้า = a a b a b a a a b a a
สตริงออก =“จํานวนของ 1 ที่พบในสายอักขระนี้ก็คือจํานวนของ baa นั่นเอง”
เครื่องมีลลี (Mealy machine) ประกอบด้วย
เซตจํากัดของสถานะ q0, q1, q2, … โดยที่ q0 เป็นสถานะเริ่มต้น
ชุดตัวอักษร Σ ของสตริงเข้า เช่น Σ = { a, b, c, … }
ชุดตัวอักษร Γ ของสตริงออก เช่น Γ = { x, y, z, … }
วงกลมแทนสถานะและเส้นเชื่อมระบุทิศทางที่ระบุถึงการผ่าน ระหว่าง สถานะ
เครื่องมีลลี ในการพิมพ์ 1’s complement ของสตริงเข้า
ถ้านําสตริงเข้า 110010 ไปประมวลผลบนเครื่องมีลลี ดังกล่าวก่อนหน้าจะได้สตริงออกคือ 001101