אוטומט הסתברותי
במתמטיקה ומדעי המחשב, אוטומט הסתברותי הוא הכללה של אוטומט סופי לא דטרמיניסטי (אסל"ד). באוטומט הסתברותי לכל מעבר בין מצבים מותאמת הסתברות, כך שמטריצת המעברים של האוטומט המתקבלת היא מטריצה סטוכסטית.
השפות המתקבלות על ידי אוטומטים הסתברותיים נקראות שפות סטוכסטיות, והן מכילות את השפות הרגולריות בתור תת-קבוצה. מספר השפות הסטוכסטיות אינו בן מנייה.
את הרעיון של אוטומט הסתברותי הציג לראשונה פרופסור מיכאל רבין ב-1963[1].
במחשוב קוונטי אוטומט סופי קוונטי הוא מקביל למונח אוטומט הסתברותי.
הערות שוליים עריכה
- ^ מיכאל רבין (1963). "Probabilistic Automata". Information and Control. 6 (3): 230–245. doi:10.1016/s0019-9958(63)90290-0. נבדק ב-27 במרץ 2015.
{{cite journal}}: (עזרה)