نظریه زبان ها و ماشین ها-کارشناسی ارشد: 

ماشین تورینگ قوی ترین ماشینی است که تا کنون بوجود اماده است و قدرت ان از همه ماشین ها یی که تا کنون خوانده اید یعنی ماشین متناهیی SFA  و ماشین پشته ای PDA  بیشتر است.ماشین تورینگ تعاریف مختلفی دارد.به طورکلی تورینگ استاندارد اتوماتایی است که حافظه ان از نوع نوار می باشد این نوار به سلول هایی تقسیم شده که هر کدام از این خانه ها توانایی ذخیره یک نماد را در خود دارد. روی این نوار هد خواندن و نوشتن قرار دارد.

این جزوه نظریه زبان ها و ماشین ها-کارشناسی ارشد به صورت دست نویس در ۸۱ صفحه  از کلاس  صفایی می باشد که دوستاران می توانند انرا به صورت مستقیم از سایت دانلو کنند.

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

دانلود با لینک مستقیم