اتوماتای احتمالاتی

اتوماتون احتمالاتی را می‌توان بر اساس بسط مفهوم اتوماتون متناهی غیر قطعی همراه با دو احتمال تعریف کرد. احتمال آنکه یک انتقال وضعیتی (state transition) همراه با وضعیت اولیه q اتفاق بیفتدکه با P آن را نمایش می‌دهیم و بعدی آنکه این وضعیت اولیه بتواند به وسیلهٔ یک بردار تصادفی(stochastic vector) که احتمال اتوماتون تصادفی را در یک وضعیت مفروض مشخص می‌سازد جایگزین شود. پس یک بردار تصادفی اولیه داریم و یک ماتریس یا بردار انتقال تصادفی که دو احتمال مفروض ما می‌باشند. یک اتوماتون متناهی غیر متعین معمولی شامل:

1. 1. یک مجموعه متناهی از وضعیت‌ها است که با ${\displaystyle Q}$
      آن را نمایش می‌دهیم.
   2. مجموعه متناهی علائم ورودی است که آن را با ${\displaystyle \mathrm{\Sigma }}$
      نمایش می‌دهیم.
   3. یک تابع انتقال است که آن را با ${\displaystyle \delta :Q\times \mathrm{\Sigma }\to P(Q),}$
      نمایش می‌دهیم.
   4. مجموعه‌ای از وضعیتهای متعین F که آن‌ها را به عنوان وضعیتهای مورد قبول یا نهایی در نظر می‌گیریم.

• در ضمن در بالا ${\displaystyle P(Q)}$
  مجموعه توانی ${\displaystyle Q}$
  می‌باشد.

با استفاده از currying تابع انتقال ${\displaystyle \delta :Q\times \mathrm{\Sigma }\to P(Q),}$

• لذا داریم: ${\displaystyle \delta (q,a,q^{\mathrm{\prime }})=1}$
  اگر ${\displaystyle q^{\mathrm{\prime }}\in \delta (q,a)}$
  و ${\displaystyle \delta (q,a,q^{\mathrm{\prime }})=0}$
  اگر ${\displaystyle q^{\mathrm{\prime }}\notin \delta (q,a)}$

حال تابع انتقال مفروض را می‌توان به صورت یک ماتریس با درایه‌های ${\displaystyle {\left[{\theta }_a\right]}_{q{q}^{\mathrm{\prime }}}=\delta (q,a,q^{\mathrm{\prime }}),}$

 * ${\displaystyle \sum _{q^{\mathrm{\prime }}}{\left[P_a\right]}_{q{q}^{\mathrm{\prime }}}=1}$

برای تمام حروف یا نشانگرهای ${\displaystyle a}$

مجموعهٔ زبان‌هایی را که به وسیلهٔ اتوماتای تصادفی شناخته می‌شوند زبان‌های تصادفی می‌نامند؛ و زبان‌های منظم از این حیث زیر مجموعه آن‌ها می‌باشند. اگر ${\displaystyle Q_{\text{accept}}}$

${\displaystyle L_{\eta }=\{s\in {\mathrm{\Sigma }}^{\ast }|v{P}_s{Q}_{\text{accept}}>\eta \}}$

یک زبان را η-stochastic می‌نامیم اگر و تنها اگر به ازای مقدار ثابت ${\displaystyle \eta }$

• هر زبان با منظمی تصادفی نیز می‌باشد و حتی قویتر از آن، هر زبان منظمی η-stochastic نیز می‌باشد. به صورت ضعیفتر هر زبان 0 -stochastic ای منظم محسوب می‌شود ولی عکس قضیه به صورت کلی برقرار نیست و زبان‌های تصادفی ای هستند که منظم محسوب نمی‌شوند.
• هر زبان η-stochasticای زبانی تصادفی محسوب می‌شود. برای مقادیر مختلف
• هر زبان تصادفی ای بوسیلهٔ اتوماتون رابین قابل بیان و نمایش می‌باشد.
• اگر ${\displaystyle \eta }$
  یک برش_نقطهٔ ایزوله باشد آنگاه ${\displaystyle L_{\eta }}$
  یک زبان منظم محسوب می‌شود.

زبانهای p-adic مثالی از زبان تصادفی را فراهم می‌کنند که منظم نیست و نیز نشان می‌دهند که تعداد زبان‌های تصادفی ناشمارا هستند. یک زبان p-adic بر روی مجموعه‌ای از رشته‌های ${\displaystyle 0,1,2,\dots ,(p-1)}$

یعنی اینکه زبان‌های p-adic صرفاً مجموعه‌ای از اعداد حقیقی هستند که بر پایهٔ p و بزرگتر از ${\displaystyle \eta }$

اتوماتون احتمالاتی یک تفسیر هندسی دارد. بردار وضعیت را می‌توان به عنوان نقطه‌ای که بر روی صفحهٔ سیپملکس استاندارد در برابر مبدأ (گوشهٔ متعامد) قرار دارد در نظر گرفت. ماتریس انتقال از یک مونوئید بر روی نقطه اعمال می‌شود. این مسئله را می‌توان بدین شکل تعمیم داد، بدین صورت که نقطهٔ را در فضای دلخواه توپولوژیکی در نظر گرفت و ماتریس‌های انتقال را از مجموعه‌ای از عملگرهای فضای توپولوژیکی در نظر گرفت پس در این حالت یک‌نیمه اتوماتون شکل می‌گیرد. مثالی از این نوع تعمیم، اتوماتون متناهی کوانتومی می‌باشد که در اینجا فضای اتوماتون توسط نقاطی روی فضای مختلط قابل تصویر نشان داده می‌شوند. درصورتی که ماتریس‌های انتقال یک مجموعه متعین هستند که از یک گروه یکتا انتخاب می‌شوند و نقطهٔ برشی به عنوان حد بیشترین مقدار زاویهٔ کوانتومی فهمیده می‌شود.

Michael O. Rabin (1963). "Probabilistic Automata". Information and Control 6 (3): 230–245. Retrieved 2۷ مارس ۲۰۱۵

Retrieved from "http://en.wikipedia.org/w/index.php?title=Probabilistic_automaton&oldid=653752600%22