سلام. سوالتون رو دقیق نفهمیدم. منظورتون [tex]L=\{a^nb^n\}[/tex] هست یا فقط رشته با a شروع میشه؟ اگه [tex]L=\{a^nb^n\}[/tex] باشه اولین a رو به # تبدیل میکنیم. به آخر رشته میریم و آخرین b رو به # تبدیل میکنیم و دوباره به اول رشته برمیگردیم. این روال اینقدر تکرار میشه که بعد از تغییر آخرین دیگه رشته ای باقی نمونه.

صورت سوال و پاسخ آن در بالا آمده است. روند کار ماشین تورینگ مانند برنامه نویسی می باشد. کسی که برنامه نویسی بلد باشد نباید در ماشین تورینگ مشکل داشته باشد. حل این سوال به همان روشی انجام می شود که بچه های مهد کودک تعداد سیب ها و پرتقال ها را بررسی می کنند که آیا با هم برابرند یا نه. فرض کنید به یک بچه مهد کودکی سوالی مکتوب داده اید و صورت سوال اینگونه است که ۵ سیب و سپس ۵ پرتقال پشت سر هم کشیده شده اند. بچه مهد کودکی که شمارش و مقایسه اعداد بلد نیست چگونه این مساله را حل می کند ؟
این کودک مداد را بر می دارد و از سمت چپ، اولین سیب را خط می زند، سپس وارد حالت فکری جدید می شود که در این حالت فکری یکی یکی میوه ها را به سمت راست با چشم خود پویش می کند تا اینکه به اولین پرتقال برسد. سپس آن را نیز خط می زند. با خط زدن این پرتقال، کودک وارد حالت فکری جدیدی می شود. اکنون از همانجایی که پرتقال را خط زده است به سمت چپ حرکت می کند و هرچه سیب ببیند نادیده می گیرد تا اینکه به محل خط زدن سیب برسد. در این حالت مداد او روی سیبی قرار دارد که قبلا خط زده بود و به ازای آن یک پرتقال نیز خط زد. حالا مداد خود را یک میوه به راست منتقل می کند و دوباره به حالت اولیه که مساله را با آن آغاز نمود وارد می شود به این معنی که فرض می کند حالا مساله مجددا از اول شروع شده است.دوباره سیبی دیگر را خط می زدن و وارد حالت فکری جدید می شود و ادامه می دهد و پرتقالی خط می زند تا اینکه همه را خط بزند.
روند application نویسی با ماشین تورینگ بسیار ساده است. فقط باید خود را جای کودکان مهدکودک در نظر بگیرید.