نظريه زبان ها و ماشين ها در نرم افزار چيست؟ | شرکت طراحي سايت بهپردازن
جواب سوال را به اين شکل بگوييم، الان در اين صفحه شما داريد با نظريه زبانها و ماشين‌ها آشنا مي‌شويد. همه اين زبانها يا کامپايلر دارد يا مفسر و بعضي هم هردو را دارا هستند. اين کامپايلر و مفسر وظيفه‌شان اين هست که دستورايي که شما براي کامپيوتر به زبان محاوره داريد داخلش مينويسيد، به زبان قابل فهم ماشين تبديل ميکند (يعني همون صفر و يک).
فرض کنيد در آينده شما مي‌خواهيد يک زبان برنامه‌نويسي طراحي و ابداع کنيد خب قبل از همه چيز بايد کامپايلر زبان خودتان را بنويسيد و به ماشين بگوييد در اين زبان هر دستور به چه شکلي هست و چه برداشتي بايد از اين دستور انجام شود. براي طراحي يک کامپايلر شما بايد با نظريه زبانها و ماشين‌ها آشنا باشيد و بلکه هم بيشتر از آشنايي بايد بدانيد.
در علوم نظريه رايانه‌ها، نظريه‌ي اتوماتا به انگليسي Automata theory يا نظريه‌ي ماشين‌ها عبارت است از بررسي رياضي ماشين‌هاي محاسبه‌گر انتزاعي و توانايي‌هاي آن‌ها براي حل مسايل. به اين ماشين‌هاي انتزاعي اتوماتا گفته ميشود. اين نظريه بسيار نزديک به نظريه زبان صوري است. به‌طوري‌که اتوماتا اغلب توسط دسته? زبان‌هاي رسمي قابل تشخيص دسته‌بندي مي‌شوند. اتوماتا نقش اساسي در طراحي کامپايلر و تجزيه کردن (parsing) ايفا ميکند. زبان‌هايي که توسط اين ماشين‌ها بررسي مي‌شوند زبان هاي فرمال هستند.
يک ماشين، يک مدل رياضي از ماشين حالات متناهي (FSM) است. يک ماشين شامل مجموعه‌اي متناهي از حالات است که بر اساس ورودي و تابع گذار خود (که مي‌تواند به صورت جدول باشد)، از يک حالت به حالت ديگر، تغيير وضعيت مي‌دهد. اين تابع انتقال به ماشين خودکار مي‌گويد که به کدام حالت بعدي با توجه به حالت فعلي و نماد داده شده، برود.
به صورت کلي، يک ماشين شامل مجموعه‌اي متناهي يا شماري از حالات مختلف است.
يک ماشين خودکار قرار است که بر روي تعدادي ورودي از دنباله يا رشته در مراحل زماني گسسته اجرا شود. در هر مرحله از زمان، ماشين يک ورودي که از مجموعه‌اي از نمادها يا حرف‌ها برداشته شده‌است را، مي‌گيرد که به آن الفبا (Alphabet) گفته ميشود. يک ماشين حاوي مجموعه‌ي متناهي از حالت هاست. در هر لحظه از اجرا بسته به نوع ماشين، مي‌تواند در يکي يا چند تا از حالت‌هايش باشد. در هر مرحله‌ي زماني، هنگامي که ماشين يک نماد را مي‌خواند، بر اساس حالت فعلي و نماد خوانده شده به حالت بعدي پرش يا گذر ميکند. اين تابع روي حالت فعلي و نماد ورودي تابع‌گذار گفته ميشود. ماشين تا زماني که يک ورودي کامل خوانده شود ورودي را نماد به نماد در دنباله‌اي مي‌خواند و از حالتي به حالت ديگر بر اساس تابع گذار، گذر ميکند. زماني که ورودي نهايي خوانده ميشود، اصطلاحاً ماشين متوقف شده‌است و به اين حالت، حالت نهايي مي‌گويند. بر اساس حالت نهايي گفته ميشود که ماشين يک ورودي را قبول يا رد کرده‌است. زير مجموعه‌اي از حالت‌هاي ماشين وجود دارد که به عنوان مجموعه‌ي حالت‌هاي مورد قبول تعريف ميشود. اگر حالت نهايي يک حالت مورد قبول باشد ماشين ورودي را پذيرفته است. در غير اين صورت ورودي رد ميشود. به مجموعه‌اي از ورودي‌ها که توسط ماشين پذيرفته ميشود زبان قابل تشخيص ماشين مي‌گويند.
همچنين به هر نماد الفبا يک حرف گفته ميشود. به عنوان مثال، الفباي لاتين {a,b،c,... ,z}=? و الفباي باينري {0و1}=? مثال‌هايي از الفبا هستند که بيشترين کاربرد را براي ما دارند.
طول رشته با علامت |w| نمايش داده ميشود و به تعداد نمادهاي موجود در رشته گفته ميشود. رشته‌ي تهي با نماد ? يا ? نمايش داده ميشود و طول آن برابر صفر در نظر گرفته ميشود. به عنوان مثال اگر w=abcc آنگاه: 4=|w|
مفاهيم اصلي مربوط به زبان ماشين و کامپيوتر شامل موارد زير ميشود :
1- عبارت هاي منظم 2- گرامرها 3- ماشين ها
لطفا براي درک موضوع مطالب زير را مطالعه بفرماييد :
الفبا: يک مجموعه متناهي و غير تهي از سمبل هايي که به هر يک از انها الفبا گفته ميشود. معمولا يک مجموعه الفبا را با نماد ? نشان ميدهند.
مثال) مجموعه الفباي زبان انگليسي
?={a,b,….,z,A,B,….,Z}
مجموعه الفباي زبان برنامه نويسي c
?={if, while,for,…}
البته توجه داريد که اين مجموعه‌ها متناهي هستند و غيرتهي .
رشته: دنباله‌اي است متناهي از عناصر الفبا يک زبان. معمولا در تعريف يک زبان از حروف انتهايي الفباي انگليسي براي نشان دادن نام رشته‌ها استفاده ميشود. در بيشتر موارد يک رشته را با نماد w نشان ميدهند. اليته اين قانون نيست بلکه مرسوم است که اين روش کار رعايت شود.
مثال)
?={a,b} ? w=ab
طول رشته: به تعداد سمبل‌هاي تشکيل دهنده يک رشته طول رشته گفته ميشود . طول رشته را معمولا به صورت | W| و گاهي اوقات به صورت n(w( نمايش ميدهند. براي زبان مثال قبلي طول رشته‌اي که در مثال آورديم ميشود 2
تعداد الفباي مشخص در رشته: تعداد الفبايي مثل a در يک رشته را با يکي از دو نمادw|a| و(na(w نشان ميدهند.
مثال ) اگر زباني داشته باشيم با الفباي ?={a,b,d} و رشته w=baadab عضو زبان باشد آنگاه ( nb(w چه مقدار خواهد بود؟ nb(w)=2
يعني تعداد تکرار حرف b در اين رشته 2 بار است
زير رشته: اگر w=xyz يک رشته باشد به گونه‌اي که*? x,y,z ? باشد، هر دنباله y يک زير رشته از w خواهد بود.
نکته: اگر رشته‌اي داراي طول n باشد، مجموعه زيررشته‌هاي آن داراي رشته‌هايي از طول صفر تا طول n خواهد بود.
مثال) اگر w=abc باشد، مجموعه زيررشته هاي آن چه خواهد بود؟
?,a,b,c,ab,bc,abc}}
?همون زير رشته با طول صفر هست.
?: بخونيد لامبدا
اگر w=xy يک رشته باشد به گونه اي که * ? x,y? آنگاه x يک پيشوند از رشته w و y يک پسوند براي w خواهد بود.
نکته: اگر w يک رشته به طول n باشد، مجموعه پيشوندها و پسوندهاي رشته w هر يک داراي n+1 عضو خواهد بود.
مثال) اگر w=aabb باشد آنگاه مجموعه پيشوندها و پسوندهاي آن داراي چند عضو خواهد بود؟
براي نوشتن مجموعه پيشوندها از سمت چپ رشته شروع مي‌کنيم و دونه به دونه يه سمبل الفبا را مي‌بينيم و در کنار سمبل‌هاي ديده شده قرار مي‌دهيم.
prefix= ?, a,aa,aab,aabb
براي نوشتن مجموعه پسوندها از سمت راست شروع به ديدن مي‌کنيم اما براي نوشتن نبايد از راست به چپ بنويسيم بلکه بايد از چپ به راست بنويسيم.
postfix=?,b,bb,abb,aabb
در زير، سه نوع از ماشين‌هاي خودکار کران‌دار ذکر شده‌است.
ماشين‌هاي خودکار کران‌دار قطعي
ماشين‌هاي خودکار کران‌دار غير قطعي
ماشين‌هاي خودکار کران‌دار غير قطعي با ?- گذار
خانواده? زبان‌هايي که با ماشين‌هاي توصيف شده در بالا پذيرفته مي‌شوند، خانواده? زبان‌هاي با قاعده ناميده مي‌شوند. هر چه يک ماشين قوي‌تر باشد، مي‌تواند زبان‌هاي پيچيده‌تري را بپذيرد. ماشين‌هاي خودکاري که از اين ماشين‌ها به‌شمار مي‌آيند، عبارتند از:
ماشين‌هاي خودکار پشته‌اي
ماشين‌هاي خودکار کران‌دار خطي
ماشين‌هاي تورينگ
براي مشاوره همين حالا با کارشناسان ما تماس بگيريد:شرکت طراحی سایت بهپردازان یک شرکت معتبر در زمینه طراحی سایت فروشگاهی، طراحی سایت شرکتی حرفه ای میباشد که آماده مشاوره رایگان در جهت توسعه کسب و کار اینترنتی میباشد.
