دانلود جزوه و نمونه سوال درس نظریه زبان ها و ماشین ها

دانلود جزوه و نمونه سوال درس نظریه زبان ها و ماشین ها

درس نظریه زبان ها و ماشین ها یکی از درس های مهم در دوره کارشناسی می باشد و همچنین پیش نیاز درس کامپایلر ها نیز می باشد که این درس را یک درس مهم تبلدیل کرده است. درس نظریه زبان ها در کنکور کارشناسی ارشد نیز جزو درس های مشترک است و در سال جاری یعنی سال 93 دروس مشترک دارای ضریب دو هستند و ضرایب آنها برایر با ضرایب دروس تخصصی برای نرم افزار است.

در علوم نظری رایانه، نظریهٔ اتوماتا (به انگلیسی: Automata theory) یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آنها برای حل مسایل. به این ماشین‌های انتزاعی اتوماتا گفته می شود. این نظریه بسیار نزدیک به نظریه زبان‌های فرمال است. به طوری که اتوماتا اغلب توسط دستهٔ زبان‌های رسمی قابل تشخیص دسته بندی می شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبان‌های فرمال هستند. برای دانلود جزوه و نمونه سوال درس نظریه زبان ها و ماشین ها به ادامه مطلب مراجعه فرمایید.

یک ماشین، یک مدل ریاضی از ماشین با حالات متناهی (FSM) است. یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که می‌تواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود.

به صورت کلی، یک ماشین شامل مجموعه‌ای متناهی یا شماری از حالات مختلف است.

در ادامه تعریفی مقدماتی از یک نوع اتوماتا ارایه می‌شود که به فهم مفاهیم ضروری مورد بحث در نظریهٔ ماشین‌ها کمک می‌کند.

تعاریف پایه نظریه ماشین‌ها
شرح غیر قراردادی
یک ماشین خودکار قرار است که بر روی تعدادی ورودی از دنباله یا رشته در مراحل زمانی گسسته اجرا شود. در هر مرحله از زمان، ماشین یک ورودی که از مجموعه‌ای از نمادها یا حرف‌ها برداشته شده‌است را، می‌گیرد که به آن الفبا (Alphabet) گفته می‌شود. یک ماشین حاوی مجموعهٔ متناهی از حالت‌هاست. در هر لحظه از اجرا بسته به نوع ماشین، می‌تواند در یکی یا چند تا از حالت‌هایش باشد. در هر مرحلهٔ زمانی، هنگامی که ماشین یک نماد را می‌خواند، بر اساس حالت فعلی و نماد خوانده شده به حالت بعدی پرش یا گذر می‌کند. این تابع روی حالت فعلی و نماد ورودی تابع گذار گفته می‌شود. ماشین تا زمانی که یک ورودی کامل خوانده شود ورودی را نماد به نماد در دنباله‌ای می‌خواند و از حالتی به حالت دیگر بر اساس تابع گذار، گذر می‌کند. زمانی که ورودی نهایی خوانده می‌شود، اصطلاحاً ماشین متوقف شده‌است و به این حالت، حالت نهایی می‌گویند. بر اساس حالت نهایی گفته می‌شود که ماشین یک ورودی را قبول یا رد کرده‌است. زیر مجموعه‌ای از حالت‌های ماشین وجود دارد که به عنوان مجموعهٔ حالت‌های مورد قبول تعریف می‌شود. اگر حالت نهایی یک حالت مورد قبول باشد ماشین ورودی را پذیرفته‌است. در غیر این صورت ورودی رد می‌شود. به مجموعه‌ای از ورودی‌ها که توسط ماشین پذیرفته می‌شود زبان قابل تشخیص ماشین می‌گویند.

شرح قراردادی
واژگان
نماد: کوچک‌ترین و بنیادی‌ترین موجودیتی که دارای معنی یا تأثیری بر ماشین است. برخی مواقع به نمادها حرف هم گفته می‌شود.
الفبا: یک مجموعه غیر تهی و متناهی از نمادها که در یک زبان تعریف شده‌اند. الفبای زبان توسط Σ نشان داده می‌شود.
همچنین به هر نماد الفبا یک حرف گفته می‌شود. به عنوان مثال،الفبای لاتین {a,b,c,…,z}=∑ و الفبای باینری {0و1}=∑ مثالهایی از الفبا هستند که بیشترین کاربرد را برای ما دارند.

کلمه یا رشته: دنباله‌ای متناهی از نمادهای یک الفباست که با عمل الحاق به هم پیوسته‌اند. به عنوان مثال english یک رشته روی الفبای زبان انگلیسی است. یک مثال از رشته به صورت مقابل است: w=aabc
طول رشته با علامت |w| نمایش داده می‌شود و به تعداد نمادهای موجود در رشته گفته می‌شود. رشته‌ی تهی با نماد ε یا ℷ نمایش داده می‌شودو طول آن برابر صفر در نظر گرفته می‌شود. به عنوان مثال اگر w=abcc آنگاه: 4=|w|

زبان: مجموعه‌ای از رشته‌ها است. این مجموعه می‌تواند متناهی یا نامتناهی باشد.