اتوماتای احتمالاتی
اتوماتای احتمالاتی در ریاضیات و علوم کامپیوتر اتوماتای احتمالاتی با حروف اختصاری PA یک نوع بسط دادن یا عمومی ساختن اتوماتای متناهی غیر قطعی (تصادفی) است که شامل احتمال یک انتقال معین و سپس تبدیل آن به یک تابع انتقال، ماتریس انتقال یا ماتریس تصادفی می‌باشد؛ بنابراین اتوماتون احتمالاتی مفهوم زنجیر مارکوف یا زیر تغییر تیپ متناهی را عمومیت می‌بخشد. زبان‌هایی که توسط اتوماتی احتمالاتی شناخته می‌شوند-_ فهم می‌شوند_ زبان‌های تصادفی نام دارند که شامل زبان‌های منظم به عنوان یک زیر مجموعه می‌شوند. تعداد زبان‌های تصادفی ناشماراست. این مفهوم در سال ۱۹۶۳ اولین بار توسط Michael O. Rabin مطرح شد. یک مورد بخصوص از آن گاهی اوقات به نام Rabin automaton شناخته می‌شود. در سال‌های اخیر نوع دیگری از این مورد، از نظر احتمالهای کوانتومی فرمول بندی شده‌است که quantum finite automaton نامیده می‌شود.
اتوماتون احتمالاتی را می‌توان بر اساس بسط مفهوم اتوماتون متناهی غیر قطعی همراه با دو احتمال تعریف کرد. احتمال آنکه یک انتقال وضعیتی (state transition) همراه با وضعیت اولیه q اتفاق بیفتدکه با P آن را نمایش می‌دهیم و بعدی آنکه این وضعیت اولیه بتواند به وسیلهٔ یک بردار تصادفی(stochastic vector) که احتمال اتوماتون تصادفی را در یک وضعیت مفروض مشخص می‌سازد جایگزین شود. پس یک بردار تصادفی اولیه داریم و یک ماتریس یا بردار انتقال تصادفی که دو احتمال مفروض ما می‌باشند. یک اتوماتون متناهی غیر متعین معمولی شامل: با استفاده از currying تابع انتقال formula_3 یک اتوماتون متناهی غیر قطعی را می‌توان به صورت یک تابع عضوی-_ membership function _ نوشت: formula_7 حال تابع انتقال مفروض را می‌توان به صورت یک ماتریس با درایه‌های formula_12 در نظر گرفت؛ لذا در این صورت ماتریس formula_13 یک ماتریس مربعی با درایه‌های صفر و یک خواهد بود که نشان می‌دهند که آیا انتقال formula_14 توسط NFA مجاز خواهد بود یا نه. چنین ماتریس انتقالی همواره برای یک اتوماتون متناهی غیر متعین تعریف می‌شود. اتوماتون احتمالاتی این ماتریس را با یک ماتریس تصادفی formula_15 جایگزین می‌کند؛ بنابراین احتمال انتقال توسط formula_16 داده می‌شود. یک تغییر وضعیت از دیگر وضعیت‌ها به هر وضعیت دیگری با احتمال یک اتفاق می‌افتد. یعنی مجموع احتمالهای انتقال برای رسیدن به هر وضعیت از وضعیتهای مجاور یک می‌شود و این بدان معناست که: برای تمام حروف یا نشانگرهای formula_18 ورودی و وضعیت‌های داخلی formula_19، وضعیت اولیه یک اتوماتون احتمالاتی توسط یک بردار ستونی formula_20 که مجموع اعضای آن برابر واحد است داده می‌شود. ماتریس تصادفی از راست عمل می‌کند بنابراین وضعیت اتوماتون تصادفی بعد از مصرف ورودی formula_21 بدین صورت خواهد بود.formula_22 در این باب باید تأکید کرد که وضعیت یک اتوماتون تصادفی همواره یک بردار تصادفی می‌باشد به این خاطر که حاصل ضرب دو ماتریس تصادفی همواره یک ماتریس تصادفی می‌باشد و البته حاصل ضرب یک بردار تصادفی و یک ماتریس تصادفی نیز یک بردار تصادفی می‌باشد. گاهی اوقات این بردار تصادفی را با تأکید بر توزیع احتمال گسسته، توزیع وضعیت‌ها می‌نامیم. به‌طور رسمی تعریف یک اتوماتون تصادفی نیازمند مکانیک اتوماتون غیر قطعی نیست که می‌تواند از آن رها شود. اساساً یک اتوماتون تصادفی formula_23 به عنوان یک چندتایی از formula_24 تعریف می‌شود. یک اتوماتون رابین، آنی است که توزیع اولیه آن یک بردار پایه باشد. (منظور از پایه همان پایهٔ فضای برداری می‌باشد) بدین معنا که تمامی مؤلفه‌های بردار مگر یکی صفر می‌باشد و آن یک مؤلفه نیز یک می‌باشد. مجموعهٔ زبان‌هایی را که به وسیلهٔ اتوماتای تصادفی شناخته می‌شوند زبان‌های تصادفی می‌نامند؛ و زبان‌های منظم از این حیث زیر مجموعه آن‌ها می‌باشند. اگر formula_25 را با سوءاستفاده از نماد گذاری برداری ستونی در نظر بگیریم که در مکان‌های متناظر با عناصر formula_25 1 (وضعیت‌های پایانی)۱ و در دیگر مکان‌ها ۰ باشد آنگاه: یک زبان را η-stochastic می‌نامیم اگر و تنها اگر به ازای مقدار ثابت formula_28، PAهایی موجود باشند که زبان را بشناسند. یک زبان را تصادفی (stochastic) گوییم اگر و تنها اگر formula_29 موجود باشد به طوری که formula_30 η-stochastic باشد. یک برش_نقطه را یک برش نقطهٔ ایزوله نامیم اگر و تنها اگر formula_31 چنان موجود باشد که formula_32 برای تمامformula_33.
زبانهای p-adic مثالی از زبان تصادفی را فراهم می‌کنند که منظم نیست و نیز نشان می‌دهند که تعداد زبان‌های تصادفی ناشمارا هستند. یک زبان p-adic بر روی مجموعه‌ای از رشته‌های formula_37 به صورت زیر تعریف می‌شود: یعنی اینکه زبان‌های p-adic صرفاً مجموعه‌ای از اعداد حقیقی هستند که بر پایهٔ p و بزرگتر از formula_28 می‌باشند. مستقیماً می‌توان نشان داد که این زبان‌ها، زبان‌هایی تصادفی هستند. اگرچه یک زبان p-adic قاعده مند محسوب می‌شود اگر و تنها اگر formula_28 گویا باشد. بخصوص از این بابت می‌توان استدلال کرد که تعداد زبان‌های تصادفی ناشمارا هستند.
اتوماتون احتمالاتی یک تفسیر هندسی دارد. بردار وضعیت را می‌توان به عنوان نقطه‌ای که بر روی صفحهٔ سیپملکس استاندارد در برابر مبداء (گوشهٔ متعامد) قرار دارد در نظر گرفت. ماتریس انتقال از یک مونوئید بر روی نقطه اعمال می‌شود. این مسئله را می‌توان بدین شکل تعمیم داد، بدین صورت که نقطهٔ را در فضای دلخواه توپولوژیکی در نظر گرفت و ماتریس‌های انتقال را از مجموعه‌ای از عملگرهای فضای توپولوژیکی در نظر گرفت پس در این حالت یک نیمه اتوماتون شکل می‌گیرد. مثالی از این نوع تعمیم، اتوماتون متناهی کوانتومی می‌باشد که در اینجا فضای اتوماتون توسط نقاطی روی فضای مختلط قابل تصویر نشان داده می‌شوند. درصورتی که ماتریس‌های انتقال یک مجموعه متعین هستند که از یک گروه یکتا انتخاب می‌شوند و نقطهٔ برشی به عنوان حد بیشترین مقدار زاویهٔ کوانتومی فهمیده می‌شود.
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