حل مثال های تبدیل زبان به ماشین های متناهی

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

رسم ماشین ازروی زبان:
قبل از اینکه من بخوام شروع کنم به مثال حل کردن میخوام یه جمله بهتون بگم. میخوام اعتراف کنم که رسم ماشین از روی زبان قاعده و قانون خاصی ندارد( این جمله عینا همون جمله ای هست که برای عبارت های منظم نویسی و گرامر نویسی به کار بردم)  و فقط به طرز برداشت شما از زبان و تجربه خودتون بستگی داره که این تجربه جز با حل مثال های زیاد به دست نمیاد . در اصل من میخوام به تجربه شما اضافه کنم یعنی میخوام براتون مثال حل کنم و خود شما که این مثال های امروز مارا یکبار دیگه  برای خودتون حل کنید تابه تجربه شما اضافه خواهد شود.  خب دیگه مقدمه کافیه و بریم سراغ حل مثال.

مثال) برای هریک از زبان های زیر DFA مناسب طراحی کنید.
 

 L1={an|n>=1}

برای کشیدن  ماشین اول باید  در زبان داده شده به من، رشته های قابل تولید این زبان را بفهمم چه خاصیتی دارند و دوم الفبا های زبان را بشناسم و بر اساس این ویژگی ها  من باید ماشین را رسم کنم. حالا چرا گفتم الفبا؟ چون در رسم dfa ما باید به ازای تک تک الفباهامون انتقال داشته  باشیم پس باید از همون اول تکلیف تعداد انتقال های هر گذر را مشخص کنیم. در این زبان الفبای زبانمون  فقط سمبل a هست پس در هر گذر من یه قاعده انتقال اونم باسمبل a باید داشته باشم.  این از اولین قدم حالا بریم سراغ رشته های مورد پذیرش این زبان . خب همون طور که خودتون هم متوجه شدید این زبان فقط داره سمبل a تولید میکنه پس ویژگی آنچنانی نداره اما یه نکته اینجا خیلی مهمه . اونم این که این زبان رشته تهی را نمیپذیره . چون شرط تعداد حداقل a را 1 گفته. پس ماشین من یه ماشین دو حالته خواهد بود چون اگر یه حالته رسم کنم همون گره شروع باید گره پایان هم باشه خب وقتی گره شروع ، گره پایان هم باشه رشته تهی هم مورد پذیرش ماشین خواهد بود اما این خلاف قانون زبان مثال خواهد بود. پس ماشین ما خواهد شد:

 L2={an|n=2k}

الفبای این زبان فقط سمبل a هست . رشته های مورد پذیرش این زبان باید تعداد زوجی از سمبل a باشد. پس این زبان یه جورایی داره  با زبون بی زبونی میگه که من رشته تهی را هم میپذیرم. چون صفر یک عدد زوج حساب میشه ( زوجیت عدد صفر را من قبلا براتون در مسئله رفع تحریم ها روشن کرده بودم)  . حالا من فرض کنید میخواهم از روی ماشین تشخیص بدهم که ایا فلان رشته موردپذیرش این زبان هست یا نه . پس باید ماشین من این خاصیت را داشته باشه که حالت پایانی اش در حالت زوج باشه تا رشته درست را بپذیره . پس یک ماشین دوحالته خواهیم داشت که فقط با سمبل a انتقال خواهد داشت :

 L3={w ԑ{a,b} * | na(w)=2k , nb(w)=2kˊ+1}

الفبای این زبان شامل a,b هست پس در هر حالت من باید دو انتقال با سمبل های a,b  داشته باشم . رشته های مورد پذیرش این زبان به این صورت خواهد بود که تعداد سمبل های a رشته هدفمون باید زوج باشه و تعداد سمبل های b همون رشته ها هم باید فرد باشه . حالا من میخواهم کار را راحت تر کنم میام اینطوری عمل میکنم که همه حالت های ممکن از نحوه چینش این سمبل ها در کنارهمدیگر را مینویسم. پس خواهیم داشت:

1-سمبل a زوج ،سمبل b زوج
2-سمبل a فرد،سمبل b فرد
3-سمبل a زوج ،سمبل b فرد
1-سمبل a فرد،سمبل b زوج

از این حالت هایی که براتون نوشتم میتونم این نتیجه را بگیرم که ماشینی که قراره براتون رسم کنم چهار حالت خواهد داشت که دقیقا در هر حالت یکی از موارد ذکر شده در بالا نوشته خواهد شد. ( اتفاق خواهد افتاد)

حالت شروع ماشینمون چون هردو سمبل در ابتدا تعدادشون تهی هست  پس  حالت هردو زوج خواهد بود.  
حالا میخوام براتون داستان کشیدن انتقال های این ماشین را بگم .( این  داستان را میتونید امشب برای خودتون به عنوان قصه قبل از خواب شب برای خودتون تعریف کنید تا خوابتون ببره)

فرض کنید در حالت شروع هستیم  یعنی سمبل a  زوج و b زوج هست(چون هردو سمبل در ابتدا طولشون صفر است)  اگر سمبلی که از رشته داریم میبینیم a بود  پس با سمبل a انتقال خواهیم داشت به حالتی که a فرد و b زوج خواهد بود.  چون در این حالت من فقط سمبل a دیدم پس a باید از حالت زوج بودن خودش خارج بشه و به حالت فرد بودن برود . حالا اگر من به جای سمبل a ، سمبل b دیده باشم ( منظورم در همون حالت شروع هست) اون موقع باید به حالتی بروم که تعداد a زوج باشد وb فرد باشد . حالا یه مرحله دیگه داستانو ادامه میدم بعد دیگه  عینا همین داستان را برای بقیه حالت ها هم تکرار میشه که به عهده خودتون خواهد بود. مثلا فکر کنید از حالت شروع با دیدن سمبل a رفتم حالت a فرد و b زوج  حالا من اگه باز سمبل a ببینم باید بروم به حالت a زوج و b زوج ( چون فقط من دارم در رشته سمبل a میبینم برای همین فقط سمبل a در حال تغییر هست و سمبل b از حالت زوج بودن خودش خارج نشده). و یا اگر من در این حالت به جای سمبل a سمبل b ببینم از حالت a فرد b زوج باید بروم به حالت a  فرد b فرد. چون یکبار من سمبل a را دیدم و بار دیگر سمبل b را دیدم پس میرسم به حالتی که هردو فرد باشد . و برای بقیه حالت ها همین داستان تکرار میشه.
اما حالت پایانی ماشین من حالتی خواهد بود که a زوج  و b فرد باشد . پس با این توضیحات  ماشین این زبان خواهد بود

الفبای این زبان a,b هست پس برای هر حالت دو انتقال باید داشته باشیم  یکی با سمبل a و دیگری با سمبل b . رشته های مورد پذیرش این زبان باید با سمبل a شروع بشه و طولشون زوج باشه. خب حتما الان باخودتون میگید که ما برای هر حالت دوتا انتقال باید داشته باشیم وبا این کار داریم به کاربر اجازه میدیم برای شروع از b هم استفاده کنه. این فکرتون کاملا درست هست برای همین من خواهم اومد در ماشین برای حالت شروع  انتقال با سمبل b را در یک حالت trap ( دام )  قرار خواهم داد.
 حالت دام حالتی هست که اولا پایانی نیست و ثانیا با همه الفباها  به خودش بر میگرده.

وقتی خواننده  بخواهد رشته را با سمبل b شروع کند مستقیم به حالت دام خواهد رفت و به هیچ عنوان نخواهد توانست رشته ای تولید کند که مورد پذیرش ماشین باشد. چون نخواهد توانست از حالت دام خارج شده و به یک حالت پایانی برسد.
اما برگردیم سراغ جریان کلی حل مثال. وقتی کاربر رشته اش را با سمبل a شروع کند باید تعداد کل رشته اش را به یک عدد زوج برساند تا مورد قبول باشه پس حالت پایانی این ماشین حالتی خواهد بود که بتواند رشته با طول زوج تولید کرده باشد . پس ماشین این گرامر خواهد شد :

الفبای این زبان 0و1 هست پس باید برای هر حالت دو انتقال با سمبل های 1و0 داشته باشیم.  برای رسم ماشین متناهی این گرامر بهتره با یه هدف ماشینو طراحی کنید . هدفتون را تولید رشته 101 بزارید و ماشینو به طوری رسم کنید که کاربر برای رسیدن به حالت پایانی حداقل یکبار مجبورباشد این زیر رشته را تولید کند. میخوام این مثالو مرحله به مرحله براتون حل کنم.
یه حالت شروع میکشیم و با الفبای 0 به خودش انتقال خواهیم کشید.

حالا با سمبل 1 انتقال به حالت بعدی را میکشیم .فقط یادتون باشه که هدفمون تولید زیر رشته 101 هست ومن میخواهم اولین 1 سمت چپ این زیر رشته را تولید کنم و در حالت جدید اگر انتقال با سمبل 1 را به حالتی جدید ببرم دیگر نخواهم توانست زیر رشته مورد نظرم را تولید کنم  برای همین باید انتقال با سمبل 0 را برای حالتی جدید قرار بدم اما از طرفی هم شاید کاربر بخواهد سمبل های 1 بیشتری در رشته اش به کار ببرد پس انتقال این حالت با سمبل 1 را به  همین حالت بر خواهم گرداند. پس خواهم داشت:

تا به اینجا من تونستم سمبل 1 زیر رشته را تولید کنم حالا باید انتقال 0 حالت دوم را به حالتی ببرم که نتیجه اش تا به الان تولید 10 باشد پس خواهیم داشت:

در این حالت اگر کاربر بخواهد به رشته 0 اضافه کند اون موقع چون زیر رشته مورد نظر ما تولید نخواهد شد و به کل زیر رشته هدف ما از بین خواهد رفت پس باید کاربر را مجاب کنیم که اگر بخواهد صفر در این مرحله در رشته قرار دهد باید برگردد به حالت اول تا دوباره مراحل تولید زیررشته 101 را طی کند اما اگر کاربر در این مرحله در رشته 1 قرار داد اون موقع زیررشته مورد نظر ما تولید و از این جا به بعد کاربر هر سمبلی میتواند قرار دهد و رشته مورد قبول نیز خواهد بود. پس  ماشین نهایی ما خواهد بود:

و اما بریم سراغ مثال اخر این بحثمون:
 

 L6={w ԑ{a,b}* | na(w) mod 3 >nb(w) mod 3 }

همون طور که در جریان هستید  باقیمانده تقسیم بر 3 همیشه بین 0 تا 2 خواهد بود . یعنی سه حالت باقیمانده خواهیم داشت . حالا این زبان داره میگه که اولا الفبای من a,b هست پس در هر حالت دو انتقال باید داشته باشیم  و تعداد سمبل هایa باقیمانده تقسیم بر 3 باید بیشتر از تعداد سمبل های b باقیمانده تقسیم بر 3 باشد . اگر گیج شدید به این عبارت توجه کنید :
من یه تعداد a  و یه تعداد b در رشته هدفم دارم . تعداد سمبل a را تقسیم بر سه میکنم یه باقیمانده ای خواهد داشت مثلا k  از طرفی تعداد سمبل های b را هم تقسیم بر 3 میکنم که این هم یه باقیمانده ای خواهد داشت مثل y . حالا رشته هایی مورد قبول این زبان و ماشین این زبان باید باشند که k از y  بیشتر باشد .

داستانی که برای زبان L3 براتون گفتم را به خاطر بیارید . عین همین داستانو من برای این ماشین میگم با اندکی تغییر تا اگر با داستان قبلی خوابتون نبرد با این یکی حتما خوابتون ببره.

حالت شروع من حالتی هست که هردو سمبل باقیمانده  0 هست . حالا فرض کنید در همین حالت : 1- من یک سمبل a  را میبینم پس باید به حالتی بروم که تعداد باقیمانده a ، 1  باشد و باقیمانده b همان 0 چون من فقط سمبل a را دیدم . 2- من به جای سمبل a سمبل b را میبینم اون موقع باید به حالتی بروم که باقیمانده a ، 0 باشد و باقیمانده b ، 1 باشد . و مابقی داستان .
حالت های پایانی  من  حالت هایی خواهند بود که باقیمانده a از باقیمانده b بیشتر باشد. پس ماشین این زبان خواهد شد:

میبینید که برخلاف ظاهر ترسناک ماشین ،خیلی راحت میشه این ماشین را رسم کرد

این از مثال های این جلسمون.  در جلسه اینده  مباحث پیرامون همین ماشین DFA را با هم بررسی خواهیم کرد.
امیدوارم خسته نشده باشید  و یادتون نرود که شرط لازم برای یادگیری این مبحث فقط تمرین زیاد هست.

ماشین DFA این زبان را رسم کنید

حسابی روی این زبان فکر کنید و سعی کنید حاصل فکرتون را روی کاغذ بیاورید. در جلسه آینده جواب این تمرین را خواهم داد.

شاد و موفق وسرحال باشید .
تا جلسه آینده خدانگهدار.