كلیه اطلاعات این سایت مربوط به شركت طراحی سایت - شركت نرم افزاری بهپردازان می باشد


موضوع مقاله : نظریه زبان ها و ماشین ها در نرم افزار چیست؟ :

شرح :

نظريه زبان ها و ماشين ها يکي از دروس تخصصي رشته نرم افزار است که معمولا از روي کتاب An Introduction to Formal Languages and Automata نوشته ي پيتر لينز تدريش ميشه و يکي از درس هايي است که کمي گنگ و گاهي بي مصرف به نظر مياد. انتشارات ناقوس اين کتاب رو منتشر کرده و حتي کتاب حل تمرينات داخل اين کتاب هم جداگانه توسط نشر ناقوس چاپ شده.

آنچه که اين کتاب به شما کمک ميکنه بياموزيد، طرز تعريف Regular Expression ها است و در اصل منطق ماشين را در هنگام دريافت ورودي ها شرح مي دهد. اينکه ماشين (تقريبا همون کامپيوتر) چگونه پيش شما شطرنج بازي ميکند و يا يک روبات چگونه يک مسير ماز را طي ميکند و بسياري از چيزهاي ديگري که شما با آن سر و کار داريد، از همين درس ساده ريشه گرفته است.

ماشين هاي DFA و NFA : در اين درس ما به ماشين هايي که داده هاي ورودي ما را تحليل ميکنند آتاماتا ميگوييم. آتاماتا ها انواع مختلفي دارند. اما نوع DFA مناسب ترين نوع آنهاست که يک مدل انتزاعي از يک کامپيوتر را مطرح ميکند. شما يک ورودي به ماشين ميدهيد. اين ماشين (همون اتاماتا) ممکن است آنرا قبول کند يا قبول نکند. اگر قبول کند اصطلاحا ميگوييم که به حالت نهايي مي رود.

براي آشنايي شما با مبحت آتاماتا ، يک ماشين DFA رو اينجا رسم کردم. کار اين ماشين قبول رشته هايي با فرمت ?*??*?(?+?)* است.
در اين فرمت از نوشتن هر چيزي که بعدش ستاره اومده يعني ميتونه کلا نباشه يا هر چند بار تکرار شه.
چيزهايي که هيچ علامتي بعدشان نيامده يعني بايد حضور داشته باشند در رشته ورودي
چيزهايي که بين آنها علامت جمع است يعني يکي از آنها انتخاب ميشود .


يک توضيح ساده تر از ورودي اي که اين ماشين مي پذيرد اين است: شما در نقطه q? هستيد و براي اينکه به حالت نهايي برويد بايد به q? برسيد. (دايره هايي که دو تا دايره دور Q کشيده شده حالت هاي نهايي هستن که اگه در اونها توقف کنيد ، يعني رشته شما پذيرفته شده). خوب اينجا بايد در مورد گراف ها بلد باشيد.

شما ميتوانيد از ته هر فلش خارج شويد و به مقصدي که فلش اشاره دارد برويد. براي رفتن روي هر فلش بايد شما ورودي تان طبق همان چيزي باشد که روي يال نوشته شده است. مثلا با ورودي ?? شما به نقطه نهايي مي رسيد. زيرا با ? به نقطه Q? ميرويد و ? که دومين کاراکتر رشته شماست، شما را توسط يالي که به Q? راه دارد به آنجا مي رساند.

حالا ميتوانيد چند حلقه را هم طي کنيد. مثلا ورودي هاي زير نيز پذيرفته ميشوند:
?????? : توجه کنيد که ? و ? قرمز ، همواره اجباري هستند و ما از حلقه اول براي توليد چند تا ? استفاده کرديم.
???????????? : در اينجا هم صفر و يک اجراي هستند و ما از حلقه اول براي توليد ? و از حلقه دوم براي توليد صفر ها استفاده کرديم.
?????????????????????????? : در اينجا ما از آخرين حلقه براي توليد تعدادي ? و ? بصورت در هم استفاده کرديم. توجه کنيد که پرانتز آخري که در (?+?)* مشاهده کرديد، نشان دهنده اين است که شما ميتونيد هر تعداد بار، اين پرانر را تکرار کنيد . علامت + در داخل پرانتر هم ميگه هر وقت ميخواي از داخل من چيزي برداري بايد يکي از اينا رو ورداري. خوب شما ميتونيد يکبار از داخل پرانتر ? و بار ديگه ? يا دوباره ? بردارين و يا چندين بار فقط ? بردارين. اين پرانتر در اصل هر رشته ي شامل ? و ? را توليد ميکند.

در نهايت ماشين ما چنين رشته هايي را مي پذيرد : که با چند تا يا هيچي يک شروع شوند و بعد يک صفر يا بيشتر پشت سر هم بيان و بعدش يه دونه ? ظاهر شود و بعدش هر چي خواست بياد.

اين يک ماشين خيلي ساده و ابتدايي DFA بود که ديدين. براي مطالعه بيشتر در مورد آتاماتا ها ميتونيد به اينجا هم مراجعه کنيد. چند نمونه گذاشته. رسم اين آتاماتا ها ، اولين پايه هاي طراحي کامپايلرهاي امروزي است. اين مباحث پايه دروسي مانند کامپايلر و هوش مصنوعي است.

 فعاليت شرکت نرم افزاري