آموزش تبدیل NFA به DFA + ساده سازی DFA [آپدیت شد]

با سلام.
خلاصه ای از  مطالبی که در چند جلسه قبل کلاس طراحی کامپایلر ها (تبدیل NFA به DFA و ساده سازی وضعیت های DFA) ارائه شد و در جلسه فردا (یکشنبه مورخ 1393/12/17) برای کوییز مطرح می شود، در اینجا تقدیم حضور شما می شود. این آموزش با ارائه دو مثال، نوشته شده است.

در ادامه مطلب با من همراه باشید.

تصاویر استفاده شده، از خروجی های نرم افزار JFLAP هستند.

اول از همه اگر خواستید می توانید ویدئوی ارائه شده آن جلسه را ببینید وگرنه در ادامه با یک مثال همه چیز توضیح داده می شود.

قبل از شروع کار بیایید ادبیات مان را یکسان کنیم! تغییر حالت ها (transition) همان یال ها (edge) هستند که روی آن ها یک یا چند حرف از حروف الفبای ماشین را می نویسیم که باعث آن تغییر حالت شده اند و به این چسباندن، Lable زدن می گویند.

مثال زیر را در نظر بگیرید:

به سادگی می توان فهمید که این یک NFA است. روش کار برای تبدیل به این صورت است که ابتدا در یک جدول، تغییر حالت ها از وضعیت های مختلف به ازای حروف الفبای ماشین را می نویسیم.

جدول برای این مثال به شکل زیر می شود:

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

جدول دوم را ببینیم! توضیحات آن بعد از تصویر آن آمده است.

در جدول دوم با استفاده از جدول اول، تکلیف DFA مشخص می شود. بدین ترتیب که ما در جدول دوم از شماره وضعیت های نوشته شده در ستون آخر (لاندا استار) وضعیت شماره 1 شروع می کنیم و وضعیت های مشاهده شده برای هر حرف از الفبا و برای هر شماره وضعیت نوشته شده (در اینجا ابتدا 1 و سپس 2) که به دنبال آن ها تعداد دلخواه از لاندا می آید را یادداشت می کنیم. زمانی که هر دو ستون و تمام حالت ها را بررسی کردیم، اگر یک یا چند دنباله از وضعیت های نوشته شده، در هر کدام از ستون ها، در سمت چپ وجود نداشت، آن را اضافه می کنیم و سپس برای ردیف (های) جدید همین کار را ادامه می دهیم تا زمانی که وضعیت های جدیدی به وجود نیاید. در واقع، این جدول به صورت پویا ساخته می شود. حالا هر دنباله از وضعیت های نوشته شده در جدول (برای نمونه 2, 1, 4, 3) با هم، یک وضعیت به حساب می آیند. حروف نوشده شده در بالای جدول، صرف نظر از دنباله آن ها (لاندا استار)، تغییر حالت های بین وضعیت ها را موجب می شوند. حالا وقت رسم DFA است. وضعیت آغازی آن همان وضعیت آغازی جدول دوم است و هر وضعیتی که یک یا چند تا از وضعیت های نهایی NFA در آن وجود داشته باشد، برای DFA وضعیت نهایی است.

هیچگاه افزودن trap به DFA (در صورت نیاز) را فراموش نکنید! پس :

+ ساده سازی DFA

قبل از ارائه مثال و توضیحات بیایید یک توافق نه چندان مهم داشته باشیم؛ برای سادگی کار ساده سازی، وضعیت trap را (در صورت وجود) نادیده  می گیریم و بعد از ساده سازی آن را (در صورت لزوم) اضافه می کنیم! حالا که توافق کردیم، مثال زیر را در نظر بگیرید (این مثال نیازی به trap ندارد) :

شاید کمی شلوغ به نظر بیاید اما برای کار ما همین لازم است! قدم اول این است که وضعیت های غیر قابل دسترسی را حذف کنیم. اگر تمام مسیر های ممکن از وضعیت آغازی به وضعیت (های) نهایی را بررسی کنیم و وضعیت های مشاهده شده را علامت بزنیم، در آخر، وضعیت (های) علامت نخورده غیر فابل دسترسی هستند و در پذیرش یا عدم پذیرش رشته های مختلف زبان آن ماشین، تاثیری ندارند. در مثال ما هم وضعیت q5، غیر قابل دسترسی است؛ پس آن را در این مرحله حذف می کنیم.

در قدم دوم، وضعیت های مختلف را به دو دسته وضعیت های نهایی و غیر نهایی، تقسیم کنیم. پس دو مجموعه {q0, q1, q2, q3, q4} و {q6, q7} را داریم. این تقسیم بندی را به این صورت ادامه می دهیم که با بررسی تغییر حالت های هر وضعیتِ داخل مجموعه های فعلی به ازای حروف مختلف الفبا، اگر تغییر یک وضعیت بر خلاف وضعیت های دیگر داخل مجموعه اش باشد، از آن مجموعه جدا می شود. بیاید یک درخت جدا سازی ببینیم و توضیحات را به شکل ساده تری ادامه دهیم.

وضعیت های q0, q1, q2, q3 با حرف a به وضعیتی از همان گروه می رسند اما q4 به وضعیت q6 می رود که از یک دسته دیگر است. پس q4 جدا می شود. q6 و q7 با حروف a و b به وضعیت هایی از همان گروه می رسند؛ پس هیچ کدام جدا نمی شوند. در مرحله بعد، از مجموعه q0, q1 ,q2, q3 با حرف a همه وضعیت ها به جز q3 به وضعیتی در همان مجموعه می رسند اما q3 به q4 می رود که از یک مجموعه دیگر است. در سطح بعدی درخت q1 هم از مجموعه q0, q1, q2 جدا می شود. اما q0 و q2 با a و با b به وضعیت هایی مختلف اما هر کدام از همان دسته تغییر حالت می دهند، پس جدا نمی شوند. یعنی q0 و q2  هر دو با a به q1 (که در واقع از یک مجموعه بودن مهم است نه برابر بودن) و با b هر دو به وضعیت دیگری ار همان مجموعه خودشان می رسند. استراتژی این بود که ابتدا اعضای یک مجموعه را برای جدا سازی به ازای ورودی a بررسی می کردیم، اگر جداشدنی در کار بود انجام می دادیم و به سطح بعد می رفتیم .گرنه به ازای b بررسی می کردیم. اگر هم در هر صورت چیزی از مجموعه جدا نمی شود، کار ما با آن مجموعه تمام شده بود.

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

در آخر، معذرت خواهی می کنم به دلیل تاخیر در انتشار و توضیحات خیلی کوتاه و مختصر!