نظریه زبان وماشین

دوست عزیز برای درک بهتر این مباحث می توانید از کتاب درس و کنکور نظریه زبان،برای کارشناسی ارشد نوشته مهندس مقسمی استفاده کنید .حجم کتاب کم است و تقریبا تمام سر فصل ها را پوشش می دهد . در کل کاملترین کتابی است که من در رابطه با این در س دیده ام.

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

اما هنوز عبارت ما کامل نیست.چون این عبارت فقط 2 تا c تولید میکنه ولی در سوال گفته شده تعداد زوج از c،بنابراین بالای عبارت

از علامت + استفاده می کنیم.+ شبیه به استار است با این تفاوت که رشته تهی رو تولید نمیکنه و به نظر من در مثال بالا به اشتباه از * استفاده شده چونکه ما باید حداقل بتونیم دو c رو تولید کنیم.پس جواب نهایی به صورت زیر نوشته میشه :

در آخر باید بگم که گزینه تقلبی در امتحان پایان ترم رو فراموش نکن چون صرف همراه داشتنش به آدم قوت قلب میده و سر امتحان نظریه بهت ایده های خوبی میده :-)

با سلام

همونطور که میدونید DFA و NFA دو پذیرنده زبانهای زبانهای منظم هستند،که DFA اتومات محدود معین و NFA اتومات محدود نامعین هست و فرق اساسی بین این دو این هستش که در DFA باید وضعیت هر حالت به ازاء تمام ورودیها مشخص باشه و به ازاء هر ورودی فقط یک حالت انتقال وجود داشته باشه در حالیکه در NFA یک یا چند حالت می تونن با ورودیهای خاص به هیچ حالتی انتقال نداشته باشن یا به چند حالت مختلف به ازاء همون ورودی انتقال انجام بدن.اما با توجه به همین تعریف سعی می کنم DFA و NFA سئوال اول رو قدم به قدم توضیح بدم :

همونطور که در صورت سئوال گفته شده تعداد a ها در عبارت باید زوج باشه و دو a پشت سرهم نباید وجود داشته باشد و همچنین حروف ورودیهای ما نیز باید از الفبای a,b,c باشد.همیشه برای رسم DFA و NFA باید ساده ترین ورودی که تمامی الفبای مارو پوشش بده استفاده کنیم و DFA یا NFA مورد نظرمون رو ابتدا برای این رشته رسم کنیم و بعد اون رو به حالات کلی تر تعمیم بدیم.در این مثال ساده ترین رشته،abca هست که موارد ذکر شده در صورت سئوال رو پوشش میده.ابتدا آتوماتا را برای این رشته ورودی ترسیم می کنیم.

همونطور که می بینید State های Q0 و Q3 شبیه هم هستن.به این State ها Final گفته میشه و در واقع در این حالت ها رشته ورودی های ما به پایان میرسه.اما سئوال اینجاست که چرا حالت آغازین ما حالت پایانی هم هست؟؟؟ در جواب باید گفت که اگر در صورت سئوال و مثال های زده شده دقت کنیم،می بینیم که گفته شده زبان مورد نظر، رشته λ(لاندا) یا همان تهی رو هم قبول میکنه،پس آتوماتای ما میتونه بدون داشتن هیچ ورودی در اولین State به پایان برسه.اما اتوماتای ما در مثال بالا a را به عنوان اولین ورودی داره پس یک حالت انتقال از q0 به q1 با دیدن ورودی a رسم می کنیم.حال ورودی های بعدی b,c هستند که یک کدام یا هردو دیده میشوند(فرقی نداره) که به ازاء اونها هم یک حالت انتقال از q1 به q2 رسم میکنیم.و در آخر یک حالت انتقال برای آخرین ورودی که همون a هست در نظر میگیریم و State آخر رو به دلیل اتمام ورودی، Final State در نظر میگیریم.ساده ترین رشته ورودی رو ساختیم اما حالا نوبت اینه که آتوماتای ما حالات کلی تری رو هم پوشش بده.

ابتدا چک میکنیم که تمامی State های ما برای ورودی b,c یک حالت انتقال داشته باشند و بعد همین کار را برای ورودی a انجام خواهیم داد.که در اینجا به تفاوت NFA و DFA که اشاره کردم میرسیم.و از اینجا به بعد مراحل ایجاد DFA رو میگم چون همونطور که گفته شد در رسم DFA باید به ازاء هر ورودی در هر حالت یک انتقال وجود داشته باشه.و بعد از اون NFA رو توضیح می دم

در شکل اول ما در State های q0,q2,q3 به ازای ورودیهای b,c هیچ حالت انتقالی نداشتیم.شکل حلقه ای که در بالای q0 و q2 رسم شده نشان دهنده تولید هر تعدادی از b,c و یا رشته تهی (λ) می باشد.که اینکار در حالت q0 تولید رشته تهی رو پوشش میده.در حالت q3 هم با دیدن b,c به حالت q0 میره که هم میتونه حالت پایانی باشه و هم میتونه رشته هایی از a,b,c رو تولید کنه.اما حالا باید چک کنیم که به ازای ورودی a در هر حالت، یک انتقال وجود داشته باشه تا DFA ما کامل بشه.

در شکل دوم در حالت های q1,q3 به ازای ورودی a انتقالی وجود نداشت و با تعیین این دو حالت انتقال،شکل کامل میشه.همونطور که می بینید با دیده شدن a در هر دو حالت q1,q3 شرط مسئله که نداشتن دو a پشت سرهم هست،نقض میشه و رشته ورودی دیگه رشته صحیحی نیست و اصطلاحا گفته میشه وارد Dead State شدیم که اون State رو با qz یا qe نشون میدیم.

در مورد NFA هم باید بگم که تمامی حالات شبیه به DFA هست و فقط چون در NFA به ازای یک ورودی میتوان هیچ انتقالی نداشت،به ازای ورودی a در حالت های q1,q3 هیچ انتقالی صورت نمی گیره و در نتیجه Dead State نداریم.

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