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

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

تعریف

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

1. 1. یک مجموعه متناهی از وضعیت‌ها است که با $\ Q\,$ آن را نمایش می‌دهیم.
   2. مجموعه متناهی علائم ورودی است که آن را با $\Sigma \,$ نمایش می‌دهیم.
   3. یک تابع انتقال است که آن را با $\delta :Q\times \Sigma \to P(Q),$ نمایش می‌دهیم.
   4. مجموعه‌ای از وضعیتهای متعین 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$ بدین صورت خواهد بود.$vP_{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\leq \eta <1$ موجود باشد به طوری که $L_{\eta }$ η-stochastic باشد. یک برش_نقطه را یک برش نقطهٔ ایزوله نامیم اگر و تنها اگر $\delta >0$ چنان موجود باشد که $\vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta$ برای تمام$s\in \Sigma ^{*}$.

ویژگی‌ها

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

زبانهای p-adic

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

 $L_{\eta }(p)=\{0.n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ and }}0.n_{1}n_{2}n_{3}\ldots >\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