אוטומט הסתברותי
קפיצה לניווט
קפיצה לחיפוש
במתמטיקה ומדעי המחשב, אוטומט הסתברותי הוא הכללה של אוטומט סופי לא דטרמיניסטי (אסל"ד). באוטומט הסתברותי לכל מעבר בין מצבים מותאמת הסתברות, כך שמטריצת המעברים של האוטומט המתקבלת היא מטריצה סטוכסטית.
השפות המתקבלות על ידי אוטומטים הסתברותיים נקראות שפות סטוכסטיות, והן מכילות את השפות הרגולריות בתור תת-קבוצה. מספר השפות הסטוכסטיות אינו בן מנייה.
את הרעיון של אוטומט הסתברותי הציג לראשונה פרופסור מיכאל רבין ב-1963[1].
במחשוב קוונטי אוטומט סופי קוונטי הוא מקביל למונח אוטומט הסתברותי.
הערות שוליים
- ^ שגיאת לואה ביחידה יחידה:Citation/CS1/Configuration בשורה 1739<includeonly></includeonly>: attempt to index field '?' (a nil value).