ในทางคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีเซมิออโตมาตอนคือออโตมาตอนจำกัดเชิงกำหนดที่มีอินพุตแต่ไม่มีเอาต์พุต ประกอบด้วยเซตQของสถานะเซต Σ ที่เรียกว่าตัวอักษรอินพุต และฟังก์ชันT : Q × Σ → Qที่เรียกว่าฟังก์ชันการเปลี่ยนสถานะ

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

ในหนังสือเก่าๆ เช่นของคลิฟฟอร์ดและเพรสตัน (1967) การกระทำของกลุ่มกึ่ง (semigroup actions ) เรียกว่า "ตัวถูกดำเนินการ (operands)"

ในทฤษฎีหมวดหมู่เซมิออโตมาตาโดยพื้นฐานแล้วคือฟังก์ชันเตอร์

เซมิกรุปการแปลงหรือโมโนอิดการแปลงคือคู่ที่ประกอบด้วยเซตQ (มักเรียกว่า "เซตของสถานะ ") และเซมิกรุปหรือโมโนอิดMของฟังก์ชันหรือ "การแปลง" ที่แมปQไปยังตัวมันเอง ฟังก์ชันเหล่านี้มีความหมายว่า สมาชิกm ทุกตัว ของMเป็นการแมปถ้าsและt เป็นฟังก์ชันสองฟังก์ชันของเซมิกรุปการแปลง ผลคูณเซมิกรุปของฟังก์ชันทั้งสองนี้จะถูกนิยามว่าเป็นการ ประกอบฟังก์ชันของฟังก์ชันทั้งสองนั้น ${\displaystyle (M,Q)}$${\displaystyle m\colon Q\to Q}$${\displaystyle (st)(q)=(s\circ t)(q)=s(t(q))}$

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

ให้Mเป็นโมโนอิดและQเป็นเซตที่ไม่ว่าง ถ้ามีการดำเนินการคูณอยู่

${\displaystyle \mu \colon Q\times M\to Q}$

${\displaystyle (q,m)\mapsto qm=\mu (q,m)}$

ซึ่งตรงตามคุณสมบัติดังกล่าว

${\displaystyle q1=q}$

สำหรับ 1 หน่วยของโมโนอิด และ

${\displaystyle q(st)=(qs)t}$

สำหรับทุกและแล้ว สามสิ่งนี้เรียกว่าการกระทำขวาMหรือเรียกสั้น ๆ ว่าการกระทำขวาในรูปแบบยาวคือการคูณขวาของสมาชิกใน Q ด้วยสมาชิกใน Mการกระทำขวามักเขียนเป็น ${\displaystyle q\in Q}$${\displaystyle s,t\in M}$${\displaystyle (Q,M,\mu )}$${\displaystyle \mu }$${\displaystyle Q_{M}}$

การกระทำทางซ้ายมีนิยามที่คล้ายคลึงกัน โดยมี

${\displaystyle \mu \colon M\times Q\to Q}$

${\displaystyle (m,q)\mapsto mq=\mu (m,q)}$

และมักจะใช้สัญลักษณ์. ${\displaystyle \,_{M}Q}$

การ กระทำแบบ Mมีความสัมพันธ์อย่างใกล้ชิดกับโมโนอิดการแปลง อย่างไรก็ตาม องค์ประกอบของMไม่จำเป็นต้องเป็นฟังก์ชันโดยตรงแต่เป็นเพียงองค์ประกอบของโมโนอิดบางตัว ดังนั้น จึงต้องกำหนดให้การกระทำนั้นสอดคล้องกับการคูณในโมโนอิด ( เช่น ) เนื่องจากโดยทั่วไปแล้ว อาจไม่เป็นไปตามนี้สำหรับบางค่า ในลักษณะเดียวกับที่ใช้ได้กับการประกอบฟังก์ชัน ${\displaystyle \mu }$${\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}$${\displaystyle \mu }$

เมื่อกำหนดเงื่อนไขนี้แล้ว ก็สามารถละวงเล็บทั้งหมดได้อย่างปลอดภัย เนื่องจากผลคูณของโมโนอิดและการกระทำของโมโนอิดบนเซตนั้นมีคุณสมบัติการสลับที่ โดยสมบูรณ์ โดยเฉพาะ อย่างยิ่ง สิ่งนี้ทำให้สามารถแทนองค์ประกอบของโมโนอิดด้วยสตริงของตัวอักษร ในความหมายของคำว่า "สตริง" ในทางวิทยาศาสตร์คอมพิวเตอร์ นามธรรมนี้ทำให้สามารถพูดถึงการดำเนินการกับสตริงโดยทั่วไปได้ และในที่สุดก็จะนำไปสู่แนวคิดของภาษาเชิงรูปธรรมที่ประกอบด้วยสตริงของตัวอักษร

ความแตกต่างอีกประการหนึ่งระหว่างM -act และโมโนอิดการแปลงคือ สำหรับM -act Q นั้น สมาชิกสองตัวที่แตกต่างกันของโมโนอิดอาจกำหนดการแปลงเดียวกันของQ ได้ หากเรากำหนดว่าสิ่งนี้จะไม่เกิดขึ้นM -act ก็จะเหมือนกับโมโนอิดการแปลงโดยพื้นฐาน แล้ว

สำหรับM -act สองตัว ที่ใช้ monoid เดียวกันM - homomorphismคือแผนที่ที่สอดคล้องกับเงื่อนไขต่อไปนี้ ${\displaystyle Q_{M}}$${\displaystyle B_{M}}$${\displaystyle M}$${\displaystyle f\colon Q_{M}\to B_{M}}$${\displaystyle f\colon Q\to B}$

${\displaystyle f(qm)=f(q)m}$

สำหรับทุกและเซตของ โฮโมมอร์ฟิซึม M ทั้งหมด มักเขียนเป็น หรือ ${\displaystyle q\in Q_{M}}$${\displaystyle m\in M}$${\displaystyle \mathrm {Hom} (Q_{M},B_{M})}$${\displaystyle \mathrm {หอม} _{M}(Q,B)}$

M - act และM -homomorphism รวมกันเป็นหมวดหมู่ที่เรียกว่าM - Act ^{[ 1 ]}

เซมิออโตมาตอนคือสามสิ่งประกอบกันโดยที่เป็นเซตที่ไม่ว่างเปล่า เรียกว่าตัวอักษรป้อนข้อมูล , Qเป็นเซตที่ไม่ว่างเปล่า เรียกว่าเซตของสถานะและTคือฟังก์ชันการเปลี่ยนสถานะ${\displaystyle (Q,\Sigma ,T)}$${\displaystyle \Sigma }$

${\displaystyle T\colon Q\times \Sigma \to Q.}$

เมื่อเซตของสถานะQเป็นเซตจำกัด—ซึ่งไม่จำเป็นต้องเป็นเช่นนั้น—เซมิออโตมาตอนอาจถูกมองว่าเป็นออโตมาตอนจำกัดเชิงกำหนด แต่ไม่มีสถานะเริ่มต้นหรือเซตของสถานะที่ยอมรับได้Aหรืออีกนัยหนึ่ง มันคือเครื่องจักรสถานะจำกัดที่ไม่มีเอาต์พุต และมีเพียงอินพุตเท่านั้น ${\displaystyle (Q,\Sigma ,T,q_{0},A)}$${\displaystyle q_{0}}$

เซมิออโตมาตอนใดๆ จะชักนำให้เกิดการกระทำของโมโนอิดในลักษณะดังต่อไปนี้

ให้เป็นโมโนอิดอิสระที่สร้างขึ้นจากตัวอักษร (โดยที่สัญลักษณ์ * เหนือตัวอักษรนั้นหมายถึงเครื่องหมายดาวคลีน ) ซึ่งเป็นเซตของสตริง ที่มีความยาวจำกัดทั้งหมด ที่ประกอบด้วยตัวอักษรใน ${\displaystyle \Sigma ^{*}}$${\displaystyle \Sigma }$${\displaystyle \Sigma }$

สำหรับทุกคำwในให้เป็นฟังก์ชันที่นิยามแบบเวียนซ้ำดังต่อไปนี้ สำหรับทุกqในQ : ${\displaystyle \Sigma ^{*}}$${\displaystyle T_{w}\colon Q\to Q}$

• ถ้าเช่นนั้นคำที่ว่างเปล่าจะไม่เปลี่ยนแปลงสถานะ${\displaystyle w=\varepsilon }$${\displaystyle T_{\varepsilon }(q)=q}$${\displaystyle \varepsilon }$
• ถ้าเป็นตัวอักษรในแล้ว${\displaystyle w=\sigma }$${\displaystyle \Sigma }$${\displaystyle T_{\sigma }(q)=T(q,\sigma )}$
• ถ้าสำหรับและแล้ว​${\displaystyle w=\sigma v}$${\displaystyle \sigma \in \Sigma }$${\displaystyle v\in \Sigma ^{*}}$${\displaystyle T_{w}(q)=T_{v}(T_{\sigma }(q))}$

ให้เป็นเซต ${\displaystyle M(Q,\Sigma ,T)}$

${\displaystyle M(Q,\Sigma ,T)=\{T_{w}\vert w\in \Sigma ^{*}\}.}$

เซตนี้ปิดภายใต้การประกอบฟังก์ชันกล่าวคือ สำหรับทุกค่าจะได้นอกจากนี้ยังประกอบด้วยซึ่งเป็นฟังก์ชันเอกลักษณ์บนQเนื่องจากการประกอบฟังก์ชันมีคุณสมบัติ การสลับ ที่ เซตนี้จึงเป็นโมโนอิด: มันถูกเรียกว่าโมโนอิดอินพุตโมโนอิดลักษณะเฉพาะเซมิกรุปลักษณะเฉพาะหรือโมโนอิดการเปลี่ยนสถานะของเซมิออโตมาตอน${\displaystyle M(Q,\Sigma ,T)}$${\displaystyle v,w\in \Sigma ^{*}}$${\displaystyle T_{w}\circ T_{v}=T_{vw}}$${\displaystyle T_{\varepsilon }}$${\displaystyle M(Q,\Sigma ,T)}$${\displaystyle (Q,\Sigma ,T)}$

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

เซตของสถานะQไม่จำเป็นต้องมีจำนวนจำกัด หรือแม้แต่สามารถนับได้ ตัวอย่างเช่น เซมิออโตมาตาเป็นพื้นฐานของแนวคิดของควอนตัมออโตมาตาจำกัดในกรณีนี้ เซตของสถานะQกำหนดโดยปริภูมิเชิงซ้อนแบบโปรเจคทีฟ และแต่ละสถานะเรียกว่าคิวบิต n สถานะการเปลี่ยนสถานะกำหนดโดย เมทริกซ์ เอกภาพn × nตัวอักษรขาเข้ายังคงมีจำนวนจำกัด และข้อกังวลทั่วไปอื่นๆ ของทฤษฎีออโตมาตายังคงมีบทบาทอยู่ ดังนั้นควอนตัมเซมิออโตมาตาอาจนิยามได้ง่ายๆ ว่าเป็นสามสิ่งเมื่อตัวอักษรมีpตัว เพื่อให้มีเมทริกซ์เอกภาพหนึ่งตัวสำหรับแต่ละตัวอักษรกล่าวโดยสรุป ควอนตัมเซมิออโตมาตามีการวางนัยทั่วไปทางเรขาคณิตมากมาย ตัวอย่างเช่น เราอาจใช้ปริภูมิสมมาตรแบบรีมันน์แทนและเลือกจากกลุ่มไอโซเมตรีเป็นฟังก์ชันการเปลี่ยนสถานะ ${\displaystyle \mathbb {C} P^{n}}$${\displaystyle \Sigma }$${\displaystyle (\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}}\})}$${\displaystyle \Sigma }$${\displaystyle U_{\sigma }}$${\displaystyle \sigma \in \Sigma }$${\displaystyle \mathbb {C} P^{n}}$

โมโนอิดเชิงไวยากรณ์ของภาษาปกติจะสมมาตรกับโมโนอิดการเปลี่ยนสถานะของออโตมาตาขั้นต่ำที่ยอมรับภาษานั้น

• AH CliffordและGB Preston , ทฤษฎีพีชคณิตของเซมิกรุปสมาคมคณิตศาสตร์อเมริกัน เล่ม 2 (1967), ISBN 978-0-8218-0272-4.
• F. Gecseg และ I. Peak, ทฤษฎีพีชคณิตของออโตมาตา (1972), Akademiai Kiado, บูดาเปสต์
• WML Holcombe, ทฤษฎีออโตมาตาเชิงพีชคณิต (1982), สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์
• JM Howie , Automata and Languages , (1991), Clarendon Press, ISBN 0-19-853442-6.
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoids, Acts and Categories (2000), Walter de Gruyter, เบอร์ลิน, ISBN 3-11-015248-7.
• Rudolf Lidl และ Günter Pilz, พีชคณิตนามธรรมประยุกต์ (1998), Springer, ISBN 978-0-387-98290-8