موضوع مقاله: اتوماتای احتمالاتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اتوماتای احتمالاتی | مقدمه: اتوماتای احتمالاتی در رایش (ریاضیات) و دانش‌های رایانه، اتوماتای احتمالاتی با حروف اختصاری PA یک نوع بسط دادن یا عمومی ساختن اتوماتای متناهی غیر قطعی (تصادفی) است که شامل احتمال یک انتقال معین و سپس تبدیل آن به یک تابع انتقال، ماتریس انتقال یا ماتریس تصادفی می‌باشد؛ بنابراین اتوماتون احتمالاتی مفهوم زنجیر مارکوف یا زیر تغییر تیپ متناهی را عمومیت می‌بخشد. | ## بخش 1: اتوماتای احتمالاتی | زبان‌هایی که توسط اتوماتی احتمالاتی شناخته می‌شوند-_ فهم می‌شوند_ زبان‌های تصادفی نام دارند که شامل زبان‌های منظم به عنوان یک زیر مجموعه می‌شوند. تعریف اتوماتون احتمالاتی را می‌توان بر اساس بسط مفهوم اتوماتون متناهی غیر قطعی همراه با دو احتمال تعریف کرد. پس یک بردار تصادفی اولیه داریم و یک ماتریس یا بردار انتقال تصادفی که دو احتمال مفروض ما می‌باشند. یک اتوماتون متناهی غیر متعین معمولی شامل: یک مجموعه متناهی از وضعیت‌ها است که با آن را نمایش می‌دهیم. مجموعه‌ای از وضعیتهای متعین F که آن‌ها را به عنوان وضعیتهای مورد قبول یا نهایی در نظر می‌گیریم. اتوماتون احتمالاتی این ماتریس را با یک ماتریس تصادفی جایگزین می‌کند؛ بنابراین احتمال انتقال توسط داده می‌شود. یک تغییر وضعیت از دیگر وضعیت‌ها به هر وضعیت دیگری با احتمال یک اتفاق می‌افتد؛ یعنی مجموع احتمالهای انتقال برای رسیدن به هر وضعیت از وضعیتهای مجاور یک می‌شود و این بدان معناست که: * برای تمام حروف یا نشانگرهای ورودی و وضعیت‌های داخلی ، وضعیت اولیه یک اتوماتون احتمالاتی توسط یک بردار ستونی که مجموع اعضای آن برابر واحد است داده می‌شود. ماتریس تصادفی از راست عمل می‌کند بنابراین وضعیت اتوماتون تصادفی بعد از مصرف ورودی بدین صورت خواهد بود. | ## بخش 2: اتوماتای احتمالاتی | در این باب باید تأکید کرد که وضعیت یک اتوماتون تصادفی همواره یک بردار تصادفی می‌باشد به این خاطر که حاصل ضرب دو ماتریس تصادفی همواره یک ماتریس تصادفی می‌باشد و البته حاصل ضرب یک بردار تصادفی و یک ماتریس تصادفی نیز یک بردار تصادفی می‌باشد. گاهی اوقات این بردار تصادفی را با تأکید بر توزیع احتمال گسسته، توزیع وضعیت‌ها می‌نامیم. به‌طور رسمی تعریف یک اتوماتون تصادفی نیازمند مکانیک اتوماتون غیر قطعی نیست که می‌تواند از آن رها شود. (منظور از پایه همان پایهٔ فضای برداری می‌باشد) بدین معنا که تمامی مؤلفه‌های بردار مگر یکی صفر می‌باشد و آن یک مؤلفه نیز یک می‌باشد. زبانهای تصادفی مجموعهٔ زبان‌هایی را که به وسیلهٔ اتوماتای تصادفی شناخته می‌شوند زبان‌های تصادفی می‌نامند؛ و زبان‌های منظم از این حیث زیر مجموعه آن‌ها می‌باشند. اگر را با سوءاستفاده از نماد گذاری برداری ستونی در نظر بگیریم که در مکان‌های متناظر با عناصر 1 (وضعیت‌های پایانی)۱ و در دیگر مکان‌ها ۰ باشد آنگاه: یک زبان را η-stochastic می‌نامیم اگر و تنها اگر به ازای مقدار ثابت ، PAهایی موجود باشند که زبان را بشناسند. یک برش_نقطه را یک برش نقطهٔ ایزوله نامیم اگر و تنها اگر چنان موجود باشد که برای تمام. به صورت ضعیفتر هر زبان 0 -stochastic ای منظم محسوب می‌شود ولی عکس قضیه به صورت کلی برقرار نیست و زبان‌های تصادفی ای هستند که منظم محسوب نمی‌شوند. | ## بخش 3: اتوماتای احتمالاتی | برای مقادیر مختلف هر زبان تصادفی ای بوسیلهٔ اتوماتون رابین قابل بیان و نمایش می‌باشد. زبانهای p-adic زبانهای p-adic مثالی از زبان تصادفی را فراهم می‌کنند که منظم نیست و نیز نشان می‌دهند که تعداد زبان‌های تصادفی ناشمارا هستند. یک زبان p-adic بر روی مجموعه‌ای از رشته‌های به صورت زیر تعریف می‌شود: یعنی اینکه زبان‌های p-adic صرفاً مجموعه‌ای از اعداد حقیقی هستند که بر پایهٔ p و بزرگتر از می‌باشند. بردار وضعیت را می‌توان به عنوان نقطه‌ای که بر روی صفحهٔ سیپملکس استاندارد در برابر مبدأ (گوشهٔ متعامد) قرار دارد در نظر گرفت. این مسئله را می‌توان بدین شکل تعمیم داد، بدین صورت که نقطهٔ را در فضای دلخواه توپولوژیکی در نظر گرفت و ماتریس‌های انتقال را از مجموعه‌ای از عملگرهای فضای توپولوژیکی در نظر گرفت پس در این حالت یک‌نیمه اتوماتون شکل می‌گیرد. مثالی از این نوع تعمیم، اتوماتون متناهی کوانتومی می‌باشد که در اینجا فضای اتوماتون توسط نقاطی روی فضای مختلط قابل تصویر نشان داده می‌شوند. | ## جمع‌بندی | درصورتی که ماتریس‌های انتقال یک مجموعه متعین هستند که از یک گروه یکتا انتخاب می‌شوند و نقطهٔ برشی به عنوان حد بیشترین مقدار زاویهٔ کوانتومی فهمیده می‌شود.