الگوریتم مارکوف

در علوم نظری کامپیوتر، الگوریتم مارکوف یک سیستم بازنویسی رشته‌ای است که قوانین گرامر-مانندی را بر روی رشته‌ای از نمادها اعمال می‌کند. الگوریتم مارکوف به عنوان یک تورینگ کامل نشان داده شده‌است که به این معنی است که آن‌ها به عنوان یک مدل کلی از یک سری محاسبات مناسب هستند که می‌توانند بیانگر هر عبارت ریاضی از علامت ساده خود باشد. الگوریتم مارکوف به نام آندرس مارکوف ریاضیدان سابق نامگذاری شده‌است.

Refal یک زبان برنامه‌نویسی مبتنی بر الگوریتم مارکوف است.

توصیف

الگوریتم‌های عادی، کلامی هستند که به عنوان کلماتی که در الفباهای مختلف به کار برده می‌شوند، در نظر گرفته می‌شود.

تعریف هر الگوریتم عادی شامل دو بخش است: یکی تعریف الفبای الگوریتم (الگوریتم برای کلمات این نمادهای الفبایی به کار برده خواهد شد) و دیگری تعریف برای طرح آن است. طرح الگوریتم عادی یک مجموعه محدود از فرمول‌هایی است که به اصطلاح به آن‌ها فرمول جایگزینی می‌گوییم که هر کدام می‌تواند ساده یا نهایی باشد. یک فرمول جایگزینی ساده کلماتی هستند به شکل $L\to D$، که $L$ و $D$ دو کلمه دلخواه در الفبای الگوریتم هستند (که به ترتیب سمت چپ و سمت راست در فرمول جایگزینی نامیده می‌شوند) به‌طور مشابه فرمول جایگزینی نهایی کلماتی هستند به شکل $L\to \cdot D$، هستند که $L$ و $D$ دو کلمه دلخواه در الفبای الگوریتم هستند. با این فرض که کاراکترهای کمکی $\to$و $\to \cdot$ ، به الفبای الگوریتم تعلق ندارند.

یک مثال از طرح الگوریتم عادی که شامل الفبای پنج حرفی $|*abc$ است می‌تواند مانند طرح زیر باشد.

${\textstyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.}$

روند استفاده از الگوریتم عادی برای یک کلمه دلخواه $V$ در الفبای الگوریتم، یک توالی گسسته از مراحل ساده است که شامل موارد زیر است. فرض کنیم $V'$ کلمه‌ای است که در مرحله قبلی الگوریتم به دست آمده‌است، (یا کلمه اصلی $V$، اگر مرحله فعلی قدم اول شماست). اگر در بین فرمول‌های جایگزینی، سمت چپی وجود نداشته باشد که شامل$V'$ باشد، کار الگوریتم تکمیل شده و نتیجه این الگوریتم کلمه $V'$ در نظر گرفته می‌شود. در غیر این صورت گزینه‌هایی هستند که در سمت چپ آن‌ها قسمتی از $V'$ ظاهر شده‌است اولین گزینه را انتخاب می‌کنیم، اگر فرمول جایگزینی یه شکل $L\to D$ باشد پس از بین تمام حالت‌های مختلفی که می‌توان $V'$ را به شکل $RLS$ نشان داد حالتی را انتخاب می‌کنیم که $R$ کوچکترین طول را داشته باشد، بعد از اعمال آن قانون نتیجه مرحله فعلی $RDS$ می‌شود و به سراغ مرحله بعد می‌رویم. حال اگر این فرمول جایگزینی به شکل $L\to \cdot D$ باشد، پس از انجام مراحل قبل که جواب آن به $RDS$ ختم می‌شود و کار الگوریتم به پایان می‌رسد.

برای مثال در طول فرایند به‌کارگیری الگوریتم با استفاده از طرح بالا، روی کلمه $|*||$ به ترتیب کلمات $|b*|$، $ba|*|$، $a|*|$، $a|b*$، $aba|*$، $baa|*$، $aa|*$، $aa|c$، $aac$، $ac|$ و $c||$ ظاهر می‌شود، پس از آن الگوریتم با نتیجه $||$ متوقف می‌شود.

هر الگوریتم عادی معادل ماشین تورینگ است و بالعکس، هر ماشین تورینگ معادل الگوریتم عادی است. یک نسخه از تز چرچ-تورینگ که در رابطه با الگوریتم عادی فرموله شده‌است، اصل نرمالیزاسیون نامیده می‌شود.

الگوریتم‌های عادی ثابت کرده‌اند که ابزار مناسبی برای ساخت بسیاری از بخش‌های برساخت‌گرایی ریاضیات هستند. علاوه بر این، به‌طور ذاتی الگوریتم‌های عادی در تعدادی از ایده‌های مربوط به اداره اطلاعات نمادها در زبان‌های برنامه‌نویسی استفاده شده‌است. به عنوان مثال در Refal

الگوریتم

قوانین توالی به صورت جفت رشته‌ها هستند. معمولاً به شکل الگوی → نشان داده می‌شوند. هر قاعده ممکن است عادی یا نهایی باشد.

با توجه به یک رشته ورودی:

1. قوانین را از بالا به پایین بررسی کنید تا ببینید که آیا هیچ‌یک از الگوهای موجود در رشته‌های ورودی یافت می‌شود.
2. در صورتی که هیچ‌کدام یافت نشود، الگوریتم متوقف می‌شود.
3. اگر یک یا بیشتر از یک قانون یافت شده‌است، از اولین آن‌ها استفاده کنید و به جای سمت چپ قانون در رشته ورودی سمت راست آن را جایگزین کنید.
4. اگر قانون استفاده شده در بالا نهایی بود. الگوریتم پایان می‌یابد.
5. برو به اول.

مثال

مثال زیر نشانگر عملیاتی ساده از الگوریتم مارکوف است.

قوانین

1. "A" -> "apple"
2. "B" -> "bag"
3. "S" -> "shop"
4. "T" -> "the"
5. "the shop" -> "my brother"
6. "a never used" -> ."terminating rule"

رشته نماد

"I bought a B of As from T S."

اجرا

اگر الگوریتم برای مثال بالا به کار برده شود، رشته نماد به روش زیر تغییر خواهد کرد.

1. "I bought a B of apples from T S."
2. "I bought a bag of apples from T S."
3. "I bought a bag of apples from T shop."
4. "I bought a bag of apples from the shop."
5. "I bought a bag of apples from my brother."

سپس الگوریتم خاتمه خواهد یافت.

مثال دیگر

این قوانین مثالی جالب تر را ارائه می‌دهد، آن‌ها اعداد دودویی را به شکل تعداد معادلی خط بازنویسی می‌کنند. به عنوان مثال ۱۰۱ به یک رشته از ۵ خط متوالی بازنویسی خواهد شد.

قوانین

1. "||۰" <- "۰|"
2. "|۰" <- "۱"
3. "" <- "۰"

رشته نماد

"۱۰۱"

اجرا

اگر الگوریتم برای مثال بالا اجرا شود. بعد از مراحل زیر الگوریتم متوقف خواهد شد.

1. "۱۰۱"
2. "۱۰|۰"
3. "۱||۰۰"
4. "|۰||۰۰"
5. "|||۰|۰۰"
6. "|||||۰۰۰"
7. "|||||۰۰"
8. "|||||۰"
9. "|||||"

جستارهای وابسته

• تووه (زبان برنامه‌نویسی)
• دستور زبان صوری

منابع

• ویکی‌پدیا انگلیسی Markov Algorithm