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