ماشین تورینگ در نظریه زبان ها و ماشین ها
مقدمه:
سلام . محمدرضا احمدآبادی هستم با جلسه دیگری از آموزش نظریه زبان ها و ماشین ها در خدمتتون هستم. امیدوارم تا به اینجا سال خوبی را شروع کرده باشید.
امروز قصد دارم براتون در مورد ماشین های تورینگ صحبت کنم . جلسه آینده به بررسی ماشین های تورینگ محاسباتی خواهیم پرداخت و جلسه بعد از آن یه سری نکات ریز در مورد ماشین های تورینگ برایتان خواهیم گفت که همان جلسه ، جلسه آخر آموزش نظریه زبان ها خواهد بود.
پس کافیه به اندازه سه جلسه من را تحمل کنید .
ماشین تورینگ:
بسیاری از زبان ها هستند که جز دسته زبان های مستقل از متن محسوب نمیشوند. مانند زبان : {anbncn|n>=0} . برای این زبان ها به هیچ عنوان نمیتوانید ماشین پشته ای استاندارد (قطعی و یا غیر قطعی) ارائه دهید. برای پذیرش رشته های این زبان ها از ماشین تورینگ استفاده میشود.
مدل انتزاعی ماشین تورینگ دارای یک نوار ورودی نامحدودو یک کنترل کننده وضعیت است که این کنترل کننده وضعیت از طریق یک هد خواندن و نوشتن به نوار دسترسی دارد .
ماشین تورینگ دارای دو ویژگی خاص می باشد:
1- هد خواندن علاوه بر خواندن سمبل های روی نوار ، میتواند روی نوار نیز بنویسد.
2- باهربار اجرای یک تابع انتقال هد میتواند یک واحد به سمت راست یا چپ حرکت کند.
تا اینجا به صورت انتزاعی گفتیم ماشین تورینگ چی هست، حالا بریم سراغ تعریف نظریه ای ماشین تورینگ:
هر تابع انتقال در یک ماشین تورینگ بیان میکند که یک حالت از ماشین به ازای یک سمبل روی نوار به چه حالت دیگری منتفل شده و چه سمبلی را روی نوار جایگزین کند و در چه جهتی حرکت کند . جهت حرکت میتواند به سمت راست (R ) و یا چپ (L) باشد.
یک تابع انتقال در یک ماشین تورینگ میتواند تابعی مانند
ᵟ(qi,a)=(qj,x,R)
که این تابع معنای آن است که اگر ماشین در حالت qi بوده و سمبل a را از رشته ورودی ببیند به حالت qj رفته و x را جایگزین a نموده و هد به سمت راست حرکت کند . برای نمایش ماشین های تورینگ نیز میتوان از گراف وضعیت استفاده کرد که در این صورت تابع فوق به صورت زیر نمایش داده میشود.
مثال) برای زبان زیر یک ماشین تورینگ رسم کنید.
L={anbn/n>=0}
برای اینکه بخواهیم یک ماشین تورینگ رسم اول باید ایده اون ماشین را پرورش بدیم . این زبان داره میگه که باید رشته های مورد پذیرش این زبان تعداد سمبل a و b مساوی داشته باشند . خب خودتون را جای کامپیوتر قرار بدید . اما کامپیوتری که شمارش بلد نیست. میخواهید رشته ورودی این زبان را کنترل کنید چه روشی به کار میبرید ؟ یادتون باشه گفتم که شما شمارش الان بلد نیستید یعنی نباید سمبل های a را بشمارید و بعد بروید سراغ شمارش سمبل های b اگر تعدادشان برابر بود یعنی مورد قبول هست. از این روش حق استفاده ندارید.
یک روش دیگری هم هست . موقعی که سنمون خیلی کم بود و شمارش بلد نبودیم چیکار میکردیم برای اینکه ببینیم ایا تعداد دو شی برابر هست یا نه؟
بله درست گفتید . یکی از اولی با یکی از دومی کنار میگذاشتیم و همین طور تا آخر این حرکت را انجام میدادیم . اگر در هر دوظرف چیزی نمی ماند انگاه میگفتیم تعدادشون برابرهست اما اگر در ظرفی چیزی مانده بودو ظرف دیگری خالی بود میگفتیم تعداد نابرابر دارند . حالا باید یه این چنین روشی را برای این مثال به کار ببریم . یعنی باید یه دونه سمبل a را بایه دونه سمبل b کنار بگذاریم و این طوری تا اخر پیش رویم اگر تعداد a و b برابر بود میگوییم رشته مورد پذیرش زبان می باشد در غیر این صورت رشته ورودی مورد پذیرش این زبان نخواهد بود.
حالا میخوام این ایده را به صورت نظریه ای بیان کنم.
در رشته ورودی من در ابتدا دو حالت ممکن هست برای من پیش بیاید. اول اینکه اصلا من هیچ سمبلی را نبینم دوم من باید اولین سمبل a را ببینم. خب وقتی من اولین سمبل a را دیدم روی اون علامت میزنم با x . بعد حرکت میکنم روبه جلو تا به اولین سمبل b برسم وقتی به اولین b رسیدم روی اون هم علامت میزنم با y. تا به اینجا یه دونه سمبل a را با یه دونه سمبل b کنار گذاشتم حالا دوباره باید برگردم به اول رشته یعنی جایی که نوشتم x. عنصر بعد از آن اگر a باشد باید دوباره کار قبل را روی اون انجام بدم . یعنی دوباره روی سمبل a دوم هم علامت x میزنم و به جلو میروم تا بعد از y سمبل b را ببینم آنگاه b را هم علامت میزنم و برمیگردم به سراغ عنصر بعد از x . اگر عنصر بعد از x ، y باشد یعنی دیگر سمبل a ندارم وباید به سمت جلو(راست) حرکت کنم تا به انتهای رشته برسم اگر در این بین به سمبل b نرسیدم یعنی تعداد سمبل های a و b باهم برابر بوده و رشته ورودی مورد پذیرش این زبان خواهد بود.
بریم سراغ رسم ماشین .
رسم ماشین تورینگ
خب تا اینجا من اولین سمبل a را در رشته میبینم . حالا باید ما بقی سمبل a را در رشته ورودی گذر کنم تا به اولین سمبل b برسم .
حالا زمانی که اولین سمبل b را ماشین مشاهده کرد باید اون را علامت بزند و برگردد به عقب (چپ) . در جریان برگشتن به سمت چپ ممکنه سمبل a را هم ماشین مشاهده کند پس از این سمبل های a هم گذر کنیم تا به سمبلx برسیم.
حالا که ما به اخرین سمبل x رسیدیم کافیه یک خانه به سمت راست حرکت کنیم تا اگر سمبل a وجود داشته باشد مشاهده کنیم. پس خواهیم داشت:
تا به اینجا ماشین یک دور کامل را زده است در دوم به بعد دیگر این رشته فقط شامل سمبل a و b تنها نخواهد بود بلکه سمبل x و y را هم در خود خواهد داشت برای اینکه این سمبل ها مشکلی در روند اصلی ماشین ایجاد نکنند ما دو قاعده به آنها اضافه میکنیم تا اگر این سمبل هارا ماشین دید از آن ها گذر کند .
حالا فرض میکنیم که بعد از اینکه به اخرین x رسیدیم سمبل بعد از x ؛ y باشد. یعنی سمبل b هست که علامت خورده. پس قاعدتا دیگر سمبل a نباید در رشته ببینیم . حالا باید سمبل های y را دونه به دونه رد کنیم و اگر به سمبل b در این بین نرسیدیم وبه انتهای رشته رسیدیم وارد حالت پایانی شویم تا رشته مورد پذیرش ماشین قرار گیرد .
اگر از همان ابتداهم به عنصر بلانک رسیده بودیم (یعنی پایان رشته)، از همان ابتدا وارد حالت پایانی میشویم تا رشته λ مورد پذیرش ماشین قرار گرفته باشد .
پس در نهایت ماشین تورینگ این زبان خواهد شد :
در اینجا به پایان این جلسه از آموزش نظریه زبان ها میرسیم . امیدوارم زیاد خسته نشده باشید .
شاد و موفق و سربلند باشید.
تا جلسه آینده خدانگهدار .
نظرات کاربران
3 سال پیش
zeinab
خیلی ممنون بخاطرآموزش خیلی خوبتون