ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ออโตมาตาเชิงความน่าจะเป็น ( PA ) เป็นการวางนัยทั่วไปของออโตมาตาจำกัดแบบไม่กำหนดโดยรวมความน่าจะเป็นของการเปลี่ยนสถานะที่กำหนดลงในฟังก์ชันการเปลี่ยนสถานะทำให้กลายเป็นเมทริกซ์การเปลี่ยนสถานะ [ ^{1 ] [ 2 ] ดังนั้น}ออโตมาตาเชิงความน่าจะเป็นจึงวางนัยทั่วไปของแนวคิดของห่วงโซ่มาร์คอฟและซับชิฟต์ของประเภทจำกัดภาษาที่ออโตมาตาเชิงความน่าจะเป็นรู้จักเรียกว่าภาษาสโตแคสติกซึ่งรวมถึงภาษาปกติเป็นเซตย่อย จำนวนของภาษาสโตแคสติกนั้นนับไม่ถ้วน

แนวคิดนี้ได้รับการแนะนำโดยMichael O. Rabinในปี พ.ศ. 2506 ^{[ 2 ]}กรณีพิเศษบางกรณีเรียกว่าออโตมาตอน Rabin (ไม่ควรสับสนกับคลาสย่อยของออโตมาตอน ωซึ่งเรียกอีกอย่างว่าออโตมาตอน Rabin) ในช่วงไม่กี่ปีที่ผ่านมา มีการกำหนดรูปแบบใหม่ขึ้นในแง่ของความน่าจะเป็นควอนตัม นั่นคือออโตมาตอนจำกัดควอนตัม

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

ในแง่หนึ่ง PA เป็นเหมือนขั้นกลางระหว่างระบบกำหนดได้แน่นอนกับระบบกำหนดไม่ได้แน่นอน เพราะมันอนุญาตให้มีสถานะถัดไปได้หลายแบบ แต่มีข้อจำกัดเกี่ยวกับน้ำหนักของสถานะเหล่านั้น อย่างไรก็ตาม นี่อาจทำให้เข้าใจผิดได้ เพราะ PA ใช้แนวคิดของจำนวนจริงในการกำหนดค่าน้ำหนัก ซึ่งไม่มีอยู่ในนิยามของทั้ง DFA และ NFA อิสรภาพเพิ่มเติมนี้ทำให้พวกมันสามารถตัดสินใจในภาษาที่ไม่ใช่ภาษาปกติได้ เช่น ภาษา p-adic ที่มีพารามิเตอร์เป็นจำนวนอตรรกยะ ดังนั้น PA จึงมีประสิทธิภาพมากกว่าทั้ง DFA และ NFA (ซึ่งเป็นที่รู้จักกันดีว่ามีประสิทธิภาพเท่ากัน)

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

สำหรับออโตมาตาจำกัดแบบไม่กำหนดทั่วไป จะมี

• เซตของสถานะที่มีจำนวนจำกัด${\displaystyle Q}$
• เซตจำกัดของสัญลักษณ์อินพุต${\displaystyle \Sigma }$
• ฟังก์ชันการเปลี่ยนผ่าน${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$
• กลุ่มของรัฐ ที่ถูก กำหนดให้เป็นรัฐที่ยอมรับ (หรือ รัฐ สุดท้าย )${\displaystyle F}$${\displaystyle F\subseteq Q}$

ใน ที่นี้หมายถึงเซตกำลังของ${\displaystyle \wp (Q)}$${\displaystyle Q}$

ด้วยการใช้หลักการเคอร์รี (currying)ฟังก์ชันการเปลี่ยนสถานะของออโตมาตาจำกัดแบบไม่กำหนด (non-deterministic finite automaton) สามารถเขียนได้ในรูปของฟังก์ชันสมาชิกภาพ (membership function)${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$

${\displaystyle \delta :Q\times \Sigma \times Q\to \{0,1\}}$

ดังนั้นหากและมิเช่นนั้น ฟังก์ชันการเปลี่ยนผ่านแบบเคอร์รีสามารถเข้าใจได้ว่าเป็นเมทริกซ์ที่มีสมาชิกเป็นเมทริกซ์ ${\displaystyle \delta (q,a,q^{\prime })=1}$${\displaystyle q^{\prime }\in \delta (q,a)}$${\displaystyle 0}$

${\displaystyle \left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q^{\prime })}$

เมทริกซ์ดังกล่าวเป็นเมทริกซ์จัตุรัส ซึ่งมีค่าเป็นศูนย์หรือหนึ่ง บ่งบอกว่าการเปลี่ยนสถานะนั้นได้รับอนุญาตจาก NFA หรือไม่ เมทริกซ์การเปลี่ยนสถานะดังกล่าวจะถูกกำหนดไว้เสมอสำหรับออโตมาตาจำกัดแบบไม่กำหนด ${\displaystyle \theta _{a}}$${\displaystyle q{\stackrel {a}{\rightarrow }}q^{\prime }}$

ออโตมาตาเชิงความน่าจะเป็นจะแทนที่เมทริกซ์เหล่านี้ด้วยตระกูลของเมทริกซ์สุ่มทางขวา สำหรับแต่ละสัญลักษณ์ a ในตัวอักษรเพื่อให้ความน่าจะเป็นของการเปลี่ยนสถานะกำหนดโดย ${\displaystyle P_{a}}$${\displaystyle \Sigma }$

${\displaystyle \left[P_{a}\right]_{qq^{\prime }}}$

การเปลี่ยนสถานะจากสถานะหนึ่งไปยังสถานะใดๆ ย่อมเกิดขึ้นด้วยความน่าจะเป็นหนึ่งอย่างแน่นอน ดังนั้นจึงต้องมีหนึ่ง

${\displaystyle \sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1}$

สำหรับตัวอักษรนำเข้าและสถานะภายใน ทั้งหมด สถานะเริ่มต้นของออโตมาตาเชิงความน่าจะเป็นจะกำหนดโดยเวกเตอร์แถวซึ่งส่วนประกอบของเวกเตอร์นั้นคือความน่าจะเป็นของสถานะเริ่มต้นแต่ละสถานะซึ่งรวมกันได้เท่ากับ 1: ${\displaystyle a}$${\displaystyle q}$${\displaystyle v}$${\displaystyle q}$

${\displaystyle \sum _{q}\left[v\right]_{q}=1}$

เมทริกซ์การเปลี่ยนสถานะทำงานทางด้านขวา ดังนั้นสถานะของออโตมาตาเชิงความน่าจะเป็น หลังจากรับสตริงอินพุตแล้วจะเป็นดังนี้ ${\displaystyle abc}$

${\displaystyle vP_{a}P_{b}P_{c}}$

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

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

ชุดของภาษาที่ระบบอัตโนมัติเชิงความน่าจะเป็นรู้จักเรียกว่าภาษาเชิงสุ่มซึ่งรวมถึงภาษาปกติเป็นส่วนย่อยด้วย

ให้เป็นเซตของสถานะ "ยอมรับ" หรือ "สุดท้าย" ของออโตมาตอน โดยการใช้สัญลักษณ์อย่างไม่เคร่งครัดอาจเข้าใจได้ว่า เป็นเวกเตอร์คอลัมน์ที่เป็นฟังก์ชันสมาชิกภาพสำหรับ; กล่าวคือ มีค่า 1 ในตำแหน่งที่สอดคล้องกับองค์ประกอบใน และมีค่า 0 ในตำแหน่งอื่น ๆ เวกเตอร์นี้สามารถหดตัวกับความน่าจะเป็นของสถานะภายใน เพื่อสร้างสเกลาร์ภาษาที่ออโตมาตอนเฉพาะรู้จักจะถูกกำหนดเป็น ${\displaystyle F=Q_{\text{accept}}\subseteq Q}$${\displaystyle Q_{\text{accept}}}$${\displaystyle Q_{\text{accept}}}$${\displaystyle Q_{\text{accept}}}$

${\displaystyle L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}>\eta \}}$

โดยที่คือเซตของสตริง ทั้งหมด ในตัวอักษร (ดังนั้น * คือเครื่องหมายดาวคลีน ) ภาษาจะขึ้นอยู่กับค่าของจุดตัดซึ่ง โดยปกติจะอยู่ในช่วง${\displaystyle \Sigma ^{*}}$${\displaystyle \Sigma }$${\displaystyle \eta }$${\displaystyle 0\leq \eta <1}$

ภาษาหนึ่งเรียกว่าภาษาη -stochasticก็ต่อเมื่อมี PA บางตัวที่รู้จักภาษานั้น สำหรับค่าคงที่ภาษาหนึ่งเรียกว่าภาษาstochasticก็ต่อเมื่อมีค่าคงที่ η บางตัว ที่ทำให้เป็น ภาษา η -stochastic ${\displaystyle \eta }$${\displaystyle 0\leq \eta <1}$${\displaystyle L_{\eta }}$

กล่าวได้ว่าจุดตัดเป็นจุดตัดโดดเดี่ยวก็ต่อเมื่อมีอยู่จริงที่ทำให้ ${\displaystyle \delta >0}$

${\displaystyle \vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta }$

สำหรับทุกคน${\displaystyle s\in \Sigma ^{*}}$

ทุกภาษาปกติล้วนเป็นภาษาเชิงสุ่ม และที่สำคัญกว่านั้น ทุกภาษาปกติเป็น ภาษาเชิงสุ่ม แบบ ηบทกลับแบบอ่อนคือ ทุกภาษาเชิงสุ่มแบบ 0 เป็นภาษาปกติ อย่างไรก็ตาม บทกลับทั่วไปนั้นไม่เป็นจริง กล่าวคือ มีภาษาเชิงสุ่มที่ไม่ใช่ภาษาปกติ

ทุก ภาษา η -stochastic เป็นภาษาสุ่ม สำหรับบางค่า ${\displaystyle 0<\eta <1}$

ภาษาเชิงสุ่มทุกภาษาสามารถแทนได้ด้วยเครื่องจักรอัตโนมัติของราบิน (Rabin automaton)

ถ้าเป็นจุดตัดที่แยกเดี่ยว แสดงว่าเป็นภาษาปกติ ${\displaystyle \eta }$${\displaystyle L_{\eta }}$

ภาษาp -adicเป็นตัวอย่างหนึ่งของภาษาเชิงสุ่มที่ไม่ใช่ภาษาปกติ และยังแสดงให้เห็นว่าจำนวนของภาษาเชิงสุ่มนั้นนับไม่ถ้วน ภาษา p -adic ถูกนิยามว่าเป็นเซตของสตริง

${\displaystyle L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ and }}0.n_{1}n_{2}n_{3}\ldots >\eta \}}$

ใน จดหมาย${\displaystyle 0,1,2,\ldots ,(p-1)}$

กล่าวคือ ภาษา p -adic เป็นเพียงเซตของจำนวนจริงใน [0, 1] ที่เขียนในฐานpโดยที่จำนวนจริงเหล่านั้นมากกว่าเป็นการง่ายที่จะแสดงให้เห็นว่า ภาษา p -adic ทั้งหมดเป็นภาษาสุ่ม^{[ 3 ]}โดยเฉพาะอย่างยิ่ง สิ่งนี้บ่งชี้ว่าจำนวนภาษาสุ่มนั้นนับไม่ได้ ภาษา p -adic เป็นภาษาปกติก็ต่อเมื่อเป็นจำนวนตรรกยะ ${\displaystyle \eta }$${\displaystyle \eta }$

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

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