اتوماتای احتمالاتی
From Wikipedia, the free encyclopedia
اتوماتای احتمالاتی در ریاضیات و علوم کامپیوتر اتوماتای احتمالاتی با حروف اختصاری PA یک نوع بسط دادن یا عمومی ساختن اتوماتای متناهی غیر قطعی (تصادفی) است که شامل احتمال یک انتقال معین و سپس تبدیل آن به یک تابع انتقال، ماتریس انتقال یا ماتریس تصادفی میباشد؛ بنابراین اتوماتون احتمالاتی مفهوم زنجیر مارکوف یا زیر تغییر تیپ متناهی را عمومیت میبخشد. زبانهایی که توسط اتوماتی احتمالاتی شناخته میشوند-_ فهم میشوند_ زبانهای تصادفی نام دارند که شامل زبانهای منظم به عنوان یک زیر مجموعه میشوند. تعداد زبانهای تصادفی ناشماراست. این مفهوم در سال ۱۹۶۳ اولین بار توسط Michael O. Rabin مطرح شد. یک مورد بخصوص از آن گاهی اوقات به نام Rabin automaton شناخته میشود. در سالهای اخیر نوع دیگری از این مورد، از نظر احتمالهای کوانتومی فرمول بندی شدهاست که quantum finite automaton نامیده میشود.