متمم DFA معکوس DFA ماشین متنهاهی غیر قطعی NFA وتبدیل NFA به DFA

1396/1/12 محمدرضا احمدآبادی 4404

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

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

چون میدونم خیلی روی این سوال فکر کردید ومطمئنا به جواب هم رسیدید فقط جواب نهایی را میگم  ببینید درست حل کردید یا نه؟

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

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

متمم DFA:


برای بدست اوردن متمم یک DFA تنها کافی است حالت پایانی به غیرپایانی و بالعکس تبدیل شود.
مثال)

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

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

معکوس یک DFA :


برای بدست آوردن معکوس یک DFA علاوه بر اینکه جهت تمامی انتقال ها را معکوس میکنیم باید حالت شروع را به پایان تبدیل شود و همه حالت های پایانی به شروع تبدیل شوند.
مثال)

[ Photo ]

[ Photo ]

ماشین متناهی غیر قطعی(NFA ) :


یک ماشین متناهی قطعی ممکن است با داشتن بعضی از شرایط عدم قطعیت  به یک ماشین متناهی غیر قطعی تبدیل شود. شرایط عدم قطعیت که در یک ماشین متناهی میتواند رخ دهد  شرایطی است که با بروز آنها در بعضی از موارد ماشین بیش از یک تصمیم گیری خواهد داشت این شرایط عدم قطعیت عبارت اند از:
1-  وجود بیش از یک حالت شروع در ماشین.
2-  وجود بیش از یک انتقال با یک سمبل الفبا برای بعضی از حالت های ماشین.
3-  عدم انتقال بعضی از حالت ها با بعضی از سمبل های الفبا.
4-  وجود انتقال  λ در ماشین.
یک NFA میتواند یک یا چندین شرط از شروط عدم قطعیت را داشته باشد.
مثال)

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

میخوام برای این زبان ماشین NFA را رسم کنم . رسم NFA خیلی راحت تر از رسم DFA هست. اگه تو یه جمله بگم اینطوری میگم:
برای رسم ماشین NFA کافیه که نگاه به شرط زبان کنید و هر انچه که به ذهنتون میاد و باخودتون مرور میکنید را روی کاغذ بیاورید.

رسم NFA دیگه مشکلات گره دام و به ازای هرالفبا یه انتقال را دیگه نداره و... هرجا به سمبلی احتیاج داشتید که حرکت کنید اون سمبل را مینویسید و هرکجا احتیاجی به سمبلی نداشتید اصلا اونو ننویسید.
برای این مثال فکر کنم همگی شما و من باهم همنظر هستیم که انتهای زبان که در سوال گفته به رشته 101 باید ختم بشه کافیه سه انتقال رسم کنیم که این رشته را تولید کنه . پس خواهیم داشت:

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

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

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

شاید الان دارید پیش خودتون فکر میکنید که ماشین NFA قوی تر از DFA هست چون همه زبان هارا نمیشد براشون DFA رسم کرد اما شاید بتونیم براشون NFA رسم کنیم . جواب این فکرتون را اخر اموزش میگم که ایا درست فکر کردید یا نه؟

وحالا بریم سراغ یه مبحث خیلی سوال خیز امتحان های نظریه:


تبدیل NFA به DFA :


دو روش برای تبدیل NFA به  DFA وجود دارد که روش اول معمولا در nfa هایی به کار برده میشوند که انتقال λ ندارند و از روش دوم برای تبدیل nfa  هایی که انتقال λ دارنداستفاده میشود.

روش اول:
در این روش ابتدا یک حالت به عنوان حالت شروع ماشین جدید ( ماشین DFA) رسم میکنیم و تمامی حالت های شروع ماشین اولیه را (NFA) را در آن مینویسیم. سپس بررسی میکنیم که این حالت جدید با هریک از سمبل های الفبا به چه حالتی انتقال دارد. اگر چنانچه حالتی با یک سمبل الفبا نتواند به هیچ حالت دیگری منتقل شود  این انتقال را در ماشین جدید  به حالت trap   قرار میدهیم . روند فوق را تا زمانی که هیچ حالت دیگری به ماشین اضافه نشود  ادامه میدهیم. در پایان هر حالتی از ماشین DFA که حداقل یک حالت پایانی از NFA را در خود دارد در ماشین DFA پایانی خواهد بود.

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

خب اول توضیح میدم و مرحله به مرحله میریم  جلو.
q 0 با سمبل 0 به خود q0 میرود پس در ماشین DFA جدید هم این انتقال را خواهیم داشت . یعنی تا به الان ماشین DFA مورد نظر ما خواهد بود:

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

حالا میرسیم به سمبل الفبای b ، q0 با سمبل b به دو حالت رفته یکی به خود q0 و دیگری به q1 پس ما یه حالت جدید ایجاد میکنیم و اسم اون حالت را میگذاریم q0q1 واز حالت q0 با سمبل 1 به این حالت یک انتقال رسم میکنیم. و خواهیم داشت:

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

حالا باید تکلیف انتقال های این حالت جدید را مشخص کنیم. حالت q0q1 باسمبل 1 به کجا رفته ؟ برای اینکه بتونیم جواب این سوالو بدیم به nfa مراجعه میکنیم و دونه به دونه هم q0با 1  و هم q1 با 1 را مشخص میکنیم که به چه حالتی رفته اند اگر این حالت را نداشتیم باید این حالت جدید را به DFA اضافه کنیم و اگر این حالت تکراری بود فقط کافی است به اون حالت یک انتقال با 1 را رسم کنیم .
خب در nfa ، q0 با سمبل 1 به q1 رفته و q1 با سمبل 1 انتقال ندارد. پس میتونیم بگیم حالت q0q1 با سمبل 1 به خودش رفته.
پس خواهیم داشت:

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

حالا باید برای حالت q0q1  تکلیف انتقال با 0 را مشخص کنیم. حالت q0 با سمبل 0 به خودش رفته و حالت q1 با سمبل 0 به حالت q2 رفته . پس در DFA جوابمون از q0q1 با سمبل 0 به q0q2 یک انتقال رسم کنیم اما این حالت را ما نداریم پس باید اول این حالت را به DFA اضافه کنیم و بعد این انتقال را رسم کنیم.

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

حالا باید تکلیف انتقال های حالت q0q2  را مشخص کنیم.   q0  با سمبل 0 به خودش میرود q2 با سمبل 0  انتقالی ندارد پس از حالت q0q2 با سمبل 0  به حالت q0 یک انتقال رسم میکنیم

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

حالا باید تکلیف انتقال با سمبل 1 را در این حالت مشخص کنیم. q0 با سمبل 1 به حالت q1  میرود  q2 با سمبل 1 به حالت q3  انتقال دارد پس ما باید یک حالت جدید به DFA اضافه کنیم به اسم q1q3 و از حالت q0q2 با سمبل 1 به این حالت یک انتقال رسم کنیم.

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

حالا باید بریم سراغ حالت q1q3. حالت q1 در NFA با سمبل 0 به حالت q2 میرود حالت q3 با سمبل 0 انتقالی ندارد  پس از حالت q1q3 با سمبل 0 به حالت q0q2 یک انتقال رسم میکنیم. اما شاید بپرسید چرا به حالت q0q1 رسم نکردم؟ در این جا باید بهتون بگم در حین حل سوال یه نگاه هم به شرط زبانتون داشته باشید . من اگر از حالت q1q3 به حالت q0q1 یک انتقال با 0 رسم کنم انگاه نمیتوانم رشته ای تولید کنم که به 101 ختم شود.

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

حالا تکلیف انتقال با سمبل 1 این حالت را مشخص کنیم. q1 با سمبل 1 انتقالی ندارد. q3 هم با سمبل 1 انتقالی ندارد. خب اما در DFA  ما باید یک انتقال برای این حالت رسم کنیم پس من باید انتقال را به جایی رسم کنم که در شرط زبانم خلالی ایجاد نشود من اگر از این حالت به q0q1 با سمبل 1 انتقال رسم کنم از شرط زبان دور نشده خواهم بود پس حالت جدیدی به وجود نیامد  در NFA حالت 3 پایانی بود پس هر حالتی که q3 داخلش باشد پایانی خواهد بود. پس در نهایت خواهیم داشت:

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

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

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

 

 

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

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

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

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

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

در این مثال از q0  توسط λ به هیچ حالتی انتقال نداریم پس من از q0 بدون دیدن الفبا میتونم فقط خود q0 را ببینم پس جواب خواهد شد:

Closure(q0)={q0}


حالا بریم سراغ حالت بعدی یعنی:

Closure(q1)


q1 با λ به q2 انتقال دارد پس علاوه بر این که خودش را بدون دیدن هیچ سمبل الفبا میتواند ببیند حالت q2 را هم بدون دیدن هیچ الفبایی میتواند ببیند. پس خواهد شد:

Closure(q1)={q1,q2}


و حالت نهایی ماشین یعنی q2 ، چون با λ هیچ انتقالی ندارد پس فقط مجموعه جواب closure(q2)  خودش خواهد شد .

Closure(q2)={q2}


حالا میاییم جدول Dtranc را رسم میکنیم. الفباهامون که 0و1 بود در ستون ها مینویسیم و حالت شروع ماشین nfa را در سطر اول جدول مینویسیم.  پس تا به الان جدول ما خواهد شد:

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

منظور من از A همون q0  بوده یعنی حالت شروع ماشین. حالا من باید  closure(move(A,0)) را حساب کنم .
از پرانتز داخلی شروع میکنم . در nfa سوال : حالت شروع با سمبل 0 به چه حالتی رفته؟

بله درست گفتید حالت q1 پس جواب پرانتز داخلی شد q1 حالا باید طبق جوابی که به دست اوردیم closure (q1) را بنویسیم، که ماقبلا این closure را بدست اورده بودیم که شده بود: {q1,q2} . اسم این حالت {q1,q2} را شما B فرض کنید .پس حالت A با سمبل 0 به حالت B منتقل شده پس در جدول در سطر A و ستون 0 ، B را خواهیم نوشت. و همچنین چون B حالت جدیدی هست ان را به سطر جدول اضافه میکنیم.  پس تا به این جا جدول ما خواهد شد :

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

حالا باید تکلیف حالت شروع با سمبل 1 را مشخص کنیم . پس باید closure(move(A,1)) را بدست بیاریم. حالت q0 در ماشین nfa با سمبل 1 به چه حالتی انتقال دارد؟ به حالت q1 . این از پرانتز داخلی حالا باید closure (q1)  را حساب کنیم که قبلا هم حساب کرده بودیم و جواب شده بود B . پس این بار حالت جدیدی به وجود نیامده پس فقط در سطر A و ستون 1 مقدار B را مینویسیم.  جدول ما تا به الان خواهد بود:

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

حالا من باید برای حالت جدید B که بود {q1,q2 } با الفباهای 0,1 تعیین تکلیف کنم. پس باید :

Closure(move(B,0))
Closure(move(B,1))


را بدست بیارم. q1  با سمبل 0 در nfa به q2 وq0 میرود q2 هم با سمبل 0 انتقالی ندارد پس

Closure(move(B,0))=closure(q0q2)


ما در بالا closure های q0 و q2 را تک تک حساب کرده بودیم حالا اگر جواب این دورا با هم اجتماع بگیریم این closure  هم به دست خواهد آمد . پس جواب ما خواهد شد:

Closure(q0q2)={q0q2}=C


حالت q0q2 یک حالت جدید هست پس اولا به سطرهامون C را اضافه میکنیم و ثانیا در قسمت Bو ستون 0 ، C را مینویسیم. پس خواهیم داشت:

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

حالا باید  
 

Closure(move(B,1))

حساب کنیم. که با توجه به nfa خواهد شد:

Closure(move(B,1))=closure(q1)=B


پس در جدول در سطر B  و ستون 1 ، B را خواهیم نوشت.

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

حالا باید تکلیف حالت C را مشخص کنیم.  با توجه به nfa  سوال خواهیم داشت:

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

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

حالا باید از روی جدول DFA را رسم کنیم . حالت سطر اول جدول حالت شروع خواهد بود و روبروی هر حالت هم هم نوع انتقال و هم خود انتقال اومده. برای تشخیص حالت پایانی به حالت پایانی nfa مراجعه کرده و حالتیکه در DFA شما این حالت را شامل میشود پایانی خواهد بود پس DFA این NFA خواهد شد:

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

واما میرسیم به سوالی که در اواسط جلسه  مطرح کرده بودم. در جواب اون سوال باید بگم ماشین NFA هیچ برتری نسبت به DFA نداره . چون الان دیگه شما یادگرفتید هر NFA که بهتون داده بشه تبدیل کنید به DFA.  پس این دوماشین در یک سطح هستند.

خب رسیدیم به اخر جلسه امروزمون .امیدوارم مطالب امروز براتون مفید بوده باشه. تمرین فراموشتون نشود

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

دانلود PDF قسمت شانزدهم آموزش نظریه زبان ها و ماشین ها

کلمات کلیدی

محمدرضا احندآبادی
مهندس نرم افزار
کارشناسی مهندسی نرم افزار
مدرس دوره نظریه زبان ها و ماشین ها