الگوریتم مارکوف کیست؟ توضیح بده.
در علوم نظری کامپیوتر، الگوریتم مارکوف یک سیستم بازنویسی رشته‌ای است که قوانین گرامر-مانندی را بر روی رشته‌ای از نمادها اعمال می‌کند. الگوریتم مارکوف به عنوان یک تورینگ کامل نشان داده شده‌است که به این معنی است که آن‌ها به عنوان یک مدل کلی از یک سری محاسبات مناسب هستند که می‌توانند بیانگر هر عبارت ریاضی از علامت ساده خود باشد. الگوریتم مارکوف به نام آندرس مارکوف ریاضیدان سابق نامگذاری شده‌است.Refal یک زبان برنامه‌نویسی مبتنی بر الگوریتم مارکوف است.توصیف.الگوریتم‌های عادی، کلامی هستند که به عنوان کلماتی که در الفباهای مختلف به کار برده می‌شوند، در نظر گرفته می‌شود.تعریف هر الگوریتم عادی شامل دو بخش است: یکی تعریف الفبای الگوریتم (الگوریتم برای کلمات این نمادهای الفبایی به کار برده خواهد شد) و دیگری تعریف برای طرح آن است. طرح الگوریتم عادی یک مجموعه محدود از فرمول‌هایی است که به اصطلاح به آن‌ها فرمول جایگزینی می‌گوییم که هر کدام می‌تواند ساده یا نهایی باشد. یک فرمول جایگزینی ساده کلماتی هستند به شکل formula_1، که formula_2 و formula_3 دو کلمه دلخواه در الفبای الگوریتم هستند (که به ترتیب سمت چپ و سمت راست در فرمول جایگزینی نامیده می‌شوند) به‌طور مشابه فرمول جایگزینی نهایی کلماتی هستند به شکل formula_4، هستند که formula_2 و formula_3 دو کلمه دلخواه در الفبای الگوریتم هستند. با این فرض که کاراکترهای کمکی formula_7و formula_8 ، به الفبای الگوریتم تعلق ندارند.یک مثال از طرح الگوریتم عادی که شامل الفبای پنج حرفی formula_9 است می‌تواند مانند طرح زیر باشد.formula_10روند استفاده از الگوریتم عادی برای یک کلمه دلخواه formula_11 در الفبای الگوریتم، یک توالی گسسته از مراحل ساده است که شامل موارد زیر است. فرض کنیم formula_12 کلمه‌ای است که در مرحله قبلی الگوریتم به دست آمده‌است، (یا کلمه اصلی formula_11، اگر مرحله فعلی قدم اول شماست). اگر در بین فرمول‌های جایگزینی، سمت چپی وجود نداشته باشد که شاملformula_12 باشد، کار الگوریتم تکمیل شده و نتیجه این الگوریتم کلمه formula_12 در نظر گرفته می‌شود. در غیر این صورت گزینه‌هایی هستند که در سمت چپ آن‌ها قسمتی از formula_12 ظاهر شده‌است اولین گزینه را انتخاب می‌کنیم، اگر فرمول جایگزینی یه شکل formula_1 باشد پس از بین تمام حالت‌های مختلفی که می‌توان formula_12 را به شکل formula_19 نشان داد حالتی را انتخاب می‌کنیم که formula_20 کوچکترین طول را داشته باشد، بعد از اعمال آن قانون نتیجه مرحله فعلی formula_21 می‌شود و به سراغ مرحله بعد می‌رویم. حال اگر این فرمول جایگزینی به شکل formula_4 باشد، پس از انجام مراحل قبل که جواب آن به formula_21 ختم می‌شود و کار الگوریتم به پایان می‌رسد.برای مثال در طول فرایند به‌کارگیری الگوریتم با استفاده از طرح بالا، روی کلمه formula_24 به ترتیب کلمات formula_25، formula_26، formula_27، formula_28، formula_29، formula_30، formula_31، formula_32، formula_33، formula_34 و formula_35 ظاهر می‌شود، پس از آن الگوریتم با نتیجه formula_36 متوقف می‌شود.هر الگوریتم عادی معادل ماشین تورینگ است و بالعکس، هر ماشین تورینگ معادل الگوریتم عادی است. یک نسخه از تز چرچ-تورینگ که در رابطه با الگوریتم عادی فرموله شده‌است، اصل نرمالیزاسیون نامیده می‌شود.الگوریتم‌های عادی ثابت کرده‌اند که ابزار مناسبی برای ساخت بسیاری از بخش‌های برساخت‌گرایی ریاضیات هستند. علاوه بر این، به‌طور ذاتی الگوریتم‌های عادی در تعدادی از ایده‌های مربوط به اداره اطلاعات نمادها در زبان‌های برنامه‌نویسی استفاده شده‌است. به عنوان مثال در Refalالگوریتم.قوانین توالی به صورت جفت رشته‌ها هستند. معمولاً به شکل الگوی → نشان داده می‌شوند. هر قاعده ممکن است عادی یا نهایی باشد.با توجه به یک رشته ورودی:مثال.مثال زیر نشانگر عملیاتی ساده از الگوریتم مارکوف است.رشته نماد."I bought a B of As from T S."اجرا.اگر الگوریتم برای مثال بالا به کار برده شود، رشته نماد به روش زیر تغییر خواهد کرد.سپس الگوریتم خاتمه خواهد یافت.مثال دیگر.این قوانین مثالی جالب تر را ارائه می‌دهد، آن‌ها اعداد دودویی را به شکل تعداد معادلی خط بازنویسی می‌کنند. به عنوان مثال ۱۰۱ به یک رشته از ۵ خط متوالی بازنویسی خواهد شد.رشته نماد."۱۰۱"اجرا.اگر الگوریتم برای مثال بالا اجرا شود. بعد از مراحل زیر الگوریتم متوقف خواهد شد.