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

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

## تعریف
اتوماتون احتمالاتی را می‌توان بر اساس بسط مفهوم اتوماتون متناهی غیر قطعی همراه با دو احتمال تعریف کرد. احتمال آنکه یک انتقال وضعیتی (state transition) همراه با وضعیت اولیه q اتفاق بیفتدکه با P آن را نمایش می‌دهیم و بعدی آنکه این وضعیت اولیه بتواند به وسیلهٔ یک بردار تصادفی(stochastic vector) که احتمال اتوماتون تصادفی را در یک وضعیت مفروض مشخص می‌سازد جایگزین شود. پس یک بردار تصادفی اولیه داریم و یک ماتریس یا بردار انتقال تصادفی که دو احتمال مفروض ما می‌باشند.
یک اتوماتون متناهی غیر متعین معمولی شامل:
## یک مجموعه متناهی از وضعیت‌ها است که با \ Q\, آن را نمایش می‌دهیم.
## مجموعه متناهی علائم ورودی است که آن را با \Sigma\, نمایش می‌دهیم.
## یک تابع انتقال است که آن را با \delta:Q\times\Sigma \to P(Q), نمایش می‌دهیم.
## مجموعه‌ای از وضعیتهای متعین F که آن‌ها را به عنوان وضعیتهای مورد قبول یا نهایی در نظر می‌گیریم.
* در ضمن در بالا \ P(Q)\, مجموعه توانی \ Q\, می‌باشد.
با استفاده از currying تابع انتقال \delta:Q\times\Sigma \to P(Q), یک اتوماتون متناهی غیر قطعی را می‌توان به صورت یک تابع عضوی-_ membership function _ نوشت: \delta:Q\times\Sigma \times Q\to \{0,1\}
* لذا داریم: \delta(q,a,q^\prime)=1 اگر q^\prime\in \delta(q,a) و \delta(q,a,q^\prime)=0 اگر q^\prime\notin \delta(q,a)
حال تابع انتقال مفروض را می‌توان به صورت یک ماتریس با درایه‌های \left[\theta_a\right]_{qq^\prime}=\delta(q,a,q^\prime), در نظر گرفت؛ لذا در این صورت ماتریس \theta_a یک ماتریس مربعی با درایه‌های صفر و یک خواهد بود که نشان می‌دهند که آیا انتقال q\stackrel{a}{\rightarrow} q^\prime توسط NFA مجاز خواهد بود یا نه. چنین ماتریس انتقالی همواره برای یک اتوماتون متناهی غیر متعین تعریف می‌شود. اتوماتون احتمالاتی این ماتریس را با یک ماتریس تصادفی P جایگزین می‌کند؛ بنابراین احتمال انتقال توسط \left[P_a\right]_{qq^\prime} داده می‌شود. یک تغییر وضعیت از دیگر وضعیت‌ها به هر وضعیت دیگری با احتمال یک اتفاق می‌افتد؛ یعنی مجموع احتمالهای انتقال برای رسیدن به هر وضعیت از وضعیتهای مجاور یک می‌شود و این بدان معناست که:
  * \sum_{q^\prime}\left[P_a\right]_{qq^\prime}=1
برای تمام حروف یا نشانگرهای a ورودی و وضعیت‌های داخلی q، وضعیت اولیه یک اتوماتون احتمالاتی توسط یک بردار ستونی v که مجموع اعضای آن برابر واحد است داده می‌شود. ماتریس تصادفی از راست عمل می‌کند بنابراین وضعیت اتوماتون تصادفی بعد از مصرف ورودی abc بدین صورت خواهد بود.v P_a P_b P_c
در این باب باید تأکید کرد که وضعیت یک اتوماتون تصادفی همواره یک بردار تصادفی می‌باشد به این خاطر که حاصل ضرب دو ماتریس تصادفی همواره یک ماتریس تصادفی می‌باشد و البته حاصل ضرب یک بردار تصادفی و یک ماتریس تصادفی نیز یک بردار تصادفی می‌باشد. گاهی اوقات این بردار تصادفی را با تأکید بر توزیع احتمال گسسته، توزیع وضعیت‌ها می‌نامیم.
به‌طور رسمی تعریف یک اتوماتون تصادفی نیازمند مکانیک اتوماتون غیر قطعی نیست که می‌تواند از آن رها شود. اساساً یک اتوماتون تصادفی PA به عنوان یک چندتایی از (Q,\Sigma,P, v, F) تعریف می‌شود. یک اتوماتون رابین، آنی است که توزیع اولیه آن یک بردار پایه باشد. (منظور از پایه همان پایهٔ فضای برداری می‌باشد) بدین معنا که تمامی مؤلفه‌های بردار مگر یکی صفر می‌باشد و آن یک مؤلفه نیز یک می‌باشد.

## زبانهای تصادفی
مجموعهٔ زبان‌هایی را که به وسیلهٔ اتوماتای تصادفی شناخته می‌شوند زبان‌های تصادفی می‌نامند؛ و زبان‌های منظم از این حیث زیر مجموعه آن‌ها می‌باشند. اگر Q_\text{accept} را با سوءاستفاده از نماد گذاری برداری ستونی در نظر بگیریم که در مکان‌های متناظر با عناصر Q_\text{accept} 1 (وضعیت‌های پایانی)۱ و در دیگر مکان‌ها ۰ باشد آنگاه:
 L_\eta = \{s\in\Sigma^* \vert vP_s Q_\text{accept} > \eta\}
یک زبان را η-stochastic می‌نامیم اگر و تنها اگر به ازای مقدار ثابت \eta، PAهایی موجود باشند که زبان را بشناسند. یک زبان را تصادفی (stochastic) گوییم اگر و تنها اگر 0\le \eta موجود باشد به طوری که L_\eta η-stochastic باشد. یک برش_نقطه را یک برش نقطهٔ ایزوله نامیم اگر و تنها اگر \delta>0 چنان موجود باشد که \vert vP(s)Q_\text{accept} - \eta \vert \ge \delta برای تمامs\in\Sigma^*.

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

## زبانهای p-adic
زبانهای p-adic مثالی از زبان تصادفی را فراهم می‌کنند که منظم نیست و نیز نشان می‌دهند که تعداد زبان‌های تصادفی ناشمارا هستند. یک زبان p-adic بر روی مجموعه‌ای از رشته‌های 0,1,2,\ldots,(p-1) به صورت زیر تعریف می‌شود:
  L_{\eta}(p)=\{0.n_1n_2n_3 \ldots \vert 0\le n_k \eta \}
یعنی اینکه زبان‌های p-adic صرفاً مجموعه‌ای از اعداد حقیقی هستند که بر پایهٔ p و بزرگتر از \eta می‌باشند. مستقیماً می‌توان نشان داد که این زبان‌ها، زبان‌هایی تصادفی هستند. اگرچه یک زبان p-adic قاعده مند محسوب می‌شود اگر و تنها اگر \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

رده:ماشین متناهی
رده:مدل‌های احتمالات
رده:نظریه اتوماتا