نظریه زبان ها و ماشین ها یکی از دروس تخصصی رشته نرم افزار است که معمولا از روی کتاب
An Introduction to Formal Languages and Automata نوشته ی پیتر لینز تدریش میشه و یکی از درس هایی است که کمی گنگ و گاهی بی مصرف به نظر میاد. انتشارات ناقوس این
کتاب رو منتشر کرده و حتی کتاب حل تمرینات داخل این کتاب هم جداگانه توسط نشر ناقوس چاپ شده.
آنچه که این کتاب به شما کمک میکنه بیاموزید، طرز تعریف
Regular Expression ها است و در اصل منطق ماشین را در هنگام دریافت ورودی ها شرح می دهد. اینکه ماشین (تقریبا همون کامپیوتر) چگونه پیش شما شطرنج بازی میکند و یا یک روبات چگونه یک مسیر ماز را طی میکند و بسیاری از چیزهای دیگری که شما با آن سر و کار دارید، از همین درس ساده ریشه گرفته است.
ماشین های DFA و NFA : در این درس ما به ماشین هایی که داده های ورودی ما را تحلیل میکنند
آتاماتا میگوییم. آتاماتا ها انواع مختلفی دارند. اما نوع DFA مناسب ترین نوع آنهاست که یک مدل انتزاعی از یک کامپیوتر را مطرح میکند. شما یک ورودی به ماشین میدهید. این ماشین (همون اتاماتا) ممکن است آنرا قبول کند یا قبول نکند. اگر قبول کند اصطلاحا میگوییم که به حالت نهایی می رود.
برای آشنایی شما با مبحت آتاماتا ، یک ماشین DFA رو اینجا رسم کردم. کار این ماشین قبول رشته هایی با فرمت
است.
*(0+1)1*00*1 در این فرمت از نوشتن هر چیزی که بعدش ستاره اومده یعنی میتونه کلا نباشه یا هر چند بار تکرار شه.چیزهایی که هیچ علامتی بعدشان نیامده یعنی باید حضور داشته باشند در رشته ورودی چیزهایی که بین آنها علامت جمع است یعنی یکی از آنها انتخاب میشود .
یک توضیح ساده تر از ورودی ای که این ماشین می پذیرد این است: شما در نقطه q0 هستید و برای اینکه به حالت نهایی بروید باید به q2 برسید. (دایره هایی که دو تا دایره دور Q کشیده شده حالت های نهایی هستن که اگه در اونها توقف کنید ، یعنی رشته شما پذیرفته شده). خوب اینجا باید در مورد گراف ها بلد باشید.
شما میتوانید از ته هر فلش خارج شوید و به مقصدی که فلش اشاره دارد بروید. برای رفتن روی هر فلش باید شما ورودی تان طبق همان چیزی باشد که روی یال نوشته شده است. مثلا با ورودی
01 شما به نقطه نهایی می رسید. زیرا با 0 به نقطه Q1 میروید و 1 که دومین کاراکتر رشته شماست، شما را توسط یالی که به Q2 راه دارد به آنجا می رساند.
حالا میتوانید چند حلقه را هم طی کنید. مثلا ورودی های زیر نیز پذیرفته میشوند:
1111
01 : توجه کنید که 0 و 1 قرمز ، همواره اجباری هستند و ما از حلقه اول برای تولید چند تا 1 استفاده کردیم.
1111
0000000
1 : در اینجا هم صفر و یک اجرای هستند و ما از حلقه اول برای تولید 1 و از حلقه دوم برای تولید صفر ها استفاده کردیم.
1111
0000000
111001101010101 : در اینجا ما از آخرین حلقه برای تولید تعدادی 0 و 1 بصورت در هم استفاده کردیم. توجه کنید که پرانتز آخری که در
*(1+0) مشاهده کردید، نشان دهنده این است که شما میتونید هر تعداد بار، این پرانر را تکرار کنید . علامت + در داخل پرانتر هم میگه هر وقت میخوای از داخل من چیزی برداری باید یکی از اینا رو ورداری. خوب شما میتونید یکبار از داخل پرانتر 0 و بار دیگه 1 یا دوباره 0 بردارین و یا چندین بار فقط 1 بردارین. این پرانتر در اصل هر رشته ی شامل 0 و 1 را تولید میکند.
در نهایت ماشین ما چنین رشته هایی را می پذیرد : که با چند تا یا هیچی یک شروع شوند و بعد یک صفر یا بیشتر پشت سر هم بیان و بعدش یه دونه 1 ظاهر شود و بعدش هر چی خواست بیاد.
این یک ماشین خیلی ساده و ابتدایی DFA بود که دیدین. برای مطالعه بیشتر در مورد آتاماتا ها میتونید به
اینجا هم مراجعه کنید. چند نمونه گذاشته. رسم این آتاماتا ها ، اولین پایه های طراحی کامپایلرهای امروزی است. این مباحث پایه دروسی مانند کامپایلر و هوش مصنوعی است.
در این آدرس میتونید
یک برنامه جاوا که آتاماتا رسم میکنه دانلود کنید. خیلی جالب و جذاب است و کار دانشجویان نرم افزار رو خیلی ساده میکنه.
منبع
