سلام دوستان
من یک سوال رو از جزوه نظریه دکتر کارگهی خوندم ولی حل سوال رو متوجه نمیشم
VOICE سر کلاس رو هم گوش دادم ولی بازم متوجه نشدم
سوال طراحی ماشین تورینگ برای زبانی هست که تعداد a و تعداد b برابر دارد و ابتدا a می آید بعد b(زبان رشته لاندا را نمیپذیرد)
من جواب سوال رو دارم (الگوریتم حل سوال)
اما متوجه نمیشم منطق استفاده از این الگوریتم چیه
لطفا برای رشته aaabbb توضیح الگوریتم رو برام بگید.ممنون(خیلی برام ضروری هست)
سلام. سوالتون رو دقیق نفهمیدم. منظورتون [tex]L=\{a^nb^n\}[/tex] هست یا فقط رشته با a شروع میشه؟ اگه [tex]L=\{a^nb^n\}[/tex] باشه اولین a رو به # تبدیل میکنیم. به آخر رشته میریم و آخرین b رو به # تبدیل میکنیم و دوباره به اول رشته برمیگردیم. این روال اینقدر تکرار میشه که بعد از تغییر آخرین دیگه رشته ای باقی نمونه.
بله منظورم زبان a^n b^n n >=1
بود
توضیح کلی الگوریتم رو که شما هم گفتید،متوجه میشم ،ولی جزییاتش رو خوب نمیفهمم،چون ریزه کاری های زیادی داره
الگوریتمش ۱۰تا تابع گذار(دلتا) داره،من برای رشته aaabbb امتحانش کردم،یعنی مرحله به مرحله برای این رشته،برای خودم نوشتمش،اما واقعا گیج شدم،چون زمانی که این درس رو پاس کردم هم،اصلا ماشین تورینگ رو بهمون درس ندادن
به نظرتون اگه از ماشین تورینگ سوال تستی طرح بشه،دونستن جزییات الگوریتم همچین سوالی لازمه؟
Sent from my ME172V using Tapatalk
(۲۰ اسفند ۱۳۹۲ ۰۳:۱۲ ب.ظ)negar.v نوشته شده توسط: بله منظورم زبان a^n b^n n >=1
بود
توضیح کلی الگوریتم رو که شما هم گفتید،متوجه میشم ،ولی جزییاتش رو خوب نمیفهمم،چون ریزه کاری های زیادی داره
الگوریتمش ۱۰تا تابع گذار(دلتا) داره،من برای رشته aaabbb امتحانش کردم،یعنی مرحله به مرحله برای این رشته،برای خودم نوشتمش،اما واقعا گیج شدم،چون زمانی که این درس رو پاس کردم هم،اصلا ماشین تورینگ رو بهمون درس ندادن
به نظرتون اگه از ماشین تورینگ سوال تستی طرح بشه،دونستن جزییات الگوریتم همچین سوالی لازمه؟
Sent from my ME172V using Tapatalk
بله جزئیات نیازه. یک نمونش سوال آخر نظریه کنکور امسال بود. معمولاً ازش سوال میاد.
روش قدم به قدم برای تست رشته aaabbb: (دو طرف رشته نال هست. یعنی رشتمون برابر ##Aaabbb## هست که حرف بزرگ نشون دهنده مکان هد ماشینه.)
حالت اول ##Aaabbb##
حالت بعدی ##Aabbb###
حالت بعدی ##aabbB###
حالت بعدی ###aabB###
حالت بعدی ###Aabb###
حالت بعدی ###Abb####
حالت بعدی ###abB####
حالت بعدی ####aB####
حالت بعدی ####Ab####
حالت بعدی ####B#####
حالت بعدی ##########
روشش رو در ارسال قبل گفتم.با خط خوردن آخرین b چون رشته ای نمیمونه به حالت نهایی میریم.
ممنون از توضیحتون
Sent from my ME172V using Tapatalk
![[تصویر: 261849_anbn.jpg]](https://img.manesht.ir/261849_anbn.jpg)
صورت سوال و پاسخ آن در بالا آمده است. روند کار ماشین تورینگ مانند برنامه نویسی می باشد. کسی که برنامه نویسی بلد باشد نباید در ماشین تورینگ مشکل داشته باشد. حل این سوال به همان روشی انجام می شود که بچه های مهد کودک تعداد سیب ها و پرتقال ها را بررسی می کنند که آیا با هم برابرند یا نه. فرض کنید به یک بچه مهد کودکی سوالی مکتوب داده اید و صورت سوال اینگونه است که ۵ سیب و سپس ۵ پرتقال پشت سر هم کشیده شده اند. بچه مهد کودکی که شمارش و مقایسه اعداد بلد نیست چگونه این مساله را حل می کند ؟
این کودک مداد را بر می دارد و از سمت چپ، اولین سیب را خط می زند، سپس وارد حالت فکری جدید می شود که در این حالت فکری یکی یکی میوه ها را به سمت راست با چشم خود پویش می کند تا اینکه به اولین پرتقال برسد. سپس آن را نیز خط می زند. با خط زدن این پرتقال، کودک وارد حالت فکری جدیدی می شود. اکنون از همانجایی که پرتقال را خط زده است به سمت چپ حرکت می کند و هرچه سیب ببیند نادیده می گیرد تا اینکه به محل خط زدن سیب برسد. در این حالت مداد او روی سیبی قرار دارد که قبلا خط زده بود و به ازای آن یک پرتقال نیز خط زد. حالا مداد خود را یک میوه به راست منتقل می کند و دوباره به حالت اولیه که مساله را با آن آغاز نمود وارد می شود به این معنی که فرض می کند حالا مساله مجددا از اول شروع شده است.دوباره سیبی دیگر را خط می زدن و وارد حالت فکری جدید می شود و ادامه می دهد و پرتقالی خط می زند تا اینکه همه را خط بزند.
روند application نویسی با ماشین تورینگ بسیار ساده است. فقط باید خود را جای کودکان مهدکودک در نظر بگیرید.
ممنون،این دفعه دیگه متوجه شدم
Sent from my ME172V using Tapatalk