• بازدید : 60 views
  • بدون نظر
این فایل در ۲۲۵اسلاید قابل ویرایش تیه شده وشامل موارد زیر است:

هدف از درس نظریه زبان ها و ماشین ها(Languages ​​and automata theory) آشنایی با نظریه محاسبات است که با مدلهای انتزاعی از ماشینها و کامپیوترها مسائل نظری مورد بررسی قرار می گیرد. زبانها، ماشینها و گرامرها سه موضوع اساسی این درس بوده و با بررسی زبانهای مختلف، گرامرهای مربوطه و ماشینهای انتزاعی مورد استفاده برای پردازش این زبانها معرفی می گردد. یک زبان صوری، انتزاعی از مشخصه های کلی زبانهای برنامه سازی است که شامل مجموعه ای از علائم و ساختارها است که تعیین کننده قالب کلی جملات است.

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

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

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

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

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

انواع ماشین‌های خودکار کراندار
در زیر، سه نوع از ماشین‌های خودکار کراندار ذکر شده است

ماشین‌های خودکار کراندار قطعی
هر وضعیت از یک ماشین خودکار از این نوع، یک گذار برای هر نشانه دارد.
ماشین‌های خودکار کراندار غیر قطعی
وضعیت‌های یک ماشین خودکار کراندار غیر قطعی، ممکن است برای هر نشانه یک گذار داشته باشد و یا اصلا انتقالی نداشته باشد و یا حتی می‌تواند برای یک نشانه، گذارهای متعددی داشته باشد. این ماشین خودکار، کلمه را در صورتی می پذیرد که حداقل یک مسیر از q0 به وضعیتی از F وجود داشته باشد. اگر گذار تعریف نشده باشد، ماشین نمی‌داند که چگونه به خواندن ورودی ادامه دهد و در نتیجه کلمه پذیرفته نمی‌شود.
ماشین‌های خودکار کراندار غیر قطعی با ε-گذار
علاوه بر اینکه می‌توانند با هر نشانه‌ای به وضعیت‌های بیشتری( یا هیچ وضعیتی) پرش کنند، این ماشین‌ها می‌توانند که به روی هیچ نشانه‌ای پرش نکنند. به این معنا که، اگر یک وضعیت گذارهای نامگذاری شده با ε را دارد، این ماشین می‌تواند در هر وضعیتی که به وسیلهٔ ε-گذار بدست آمده قرار گیرد که این کار می‌تواند با واسطه یا بدون واسطهٔ وضعیت‌های دیگر صورت گیرد. مجموعهٔ وضعیت هایی که می‌توان به وسیلهٔ این شیوه از وضعیت q بدست آورد، ε-بستار برای q نامیده می‌شود.
با این وجود می‌توان نشان داد که تمام این ماشین ها، می‌توانند زبان‌های مشابهی را بپذیرند.

گسترهٔ ماشین‌های متناهی
خانوادهٔ زبان هایی که با ماشین‌های توصیف شده در بالا پذیرفته می‌شوند، خانوادهٔ زبان‌های باقاعده نامیده می‌شوند. هر چه یک ماشین قوی تر باشد، می‌تواند زبان‌های پیچیده تری را بپذیرد.

ماشین‌های خودکار این چنینی عبارتند از:

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

عتیقه زیرخاکی گنج