پاورپوینت آموزشی نظریه زبانها و ماشینها رشته مهندسی کامپیوتر

پاورپوینت آموزشی دانشگاهی با عنوان نظریه زبانها و ماشینها در قالب فایل PPT با 225 صفحه محتوا برای دانشجویان رشته مهندسی کامپیوتر و فناوری اطلاعات توسط یکی از اساتید محترم دانشگاهی جهت آموزش گردآوری شده است. در ادامه بخش هایی از این پاورپوینت به همراه فهرست مطالب آن را مشاهده خواهید کرد.

لازم به توضیح است که این پاورپوینت کلیه مباحث واحد درسی نظریه زبان ها و ماشین ها (منبع کتاب Languages & machines Written By: Thomas A.Sudkamp ) را به همراه فرمول و مثال های کامل و جامع توضیح و آموزش داده است.

گراف ها

• گراف جهت دار: اگر هر لبه گراف دارای جهت باشد به آن گراف جهت دار(digraph) می گویند.
• گراف وزن دار: اگر به لبه ها مقادیری تخصیص یافته باشدبه آن مقادیر وزن و به آن گراف،گراف وزن دار می گوییم.
• مسیر (path): در یک گراف جهت داربه دنباله ای از گره ها که بین هر گره و گره بعدی یک لبه وجود داشته باشد گفته می شود.
• چرخه (cycle): به مسیری که از یک گره شروع شده و به خودش باز می گردد گفته می شود.
• گراف چرخه ای: اگر گرافی شامل یک چرخه باشد به آن گراف چرخه ای گفته می شود.
• گراف بدون جهت: گرافی که لبه های ان هیچ جهتی نداشته باشند.
• گراف متصل: گرافی بدون جهت که بین هر دو گره دلخواه از آن یک مسیر مشخص وجود داشته باشد.

رشته ها و زبانها

• زبان: یک زبان یک مجموعه از رشته ها روی یک الفبا است.
• رشته: یک رشته روی یک مجموعه X یک دنباله متناهی از عناصرY است.
• الفبای زبان: به مجموعه عناصری که رشته ها از آن ساخته می شوند الفبای زبان گوئیم.
• رشته تهی: رشته فاقد عنصر را رشته تهی می نامیم که با λ نشان می دهیم.

گرامر مستقل از متن

یک گرامر مستقل از متن، یک چهارتایی (V,∑,P,S) است که درآن V یک مجموعه متناهی از متغیرها،∑ (الفبا) یک مجموعه متناهی از عناصر پایانی، P یک مجموعه متناهی از قوانین و S یک عنصر مشخص از V به نام عنصر ابتدایی است.

عناصر غیر مفید

یک عنصر پایانی مفید است اگر در یک رشته از زبان G رخ دهد. یک متغیر مفید است اگر در یک اشتقاق که با یک عنصر ابتدائی شروع شده و یک رشته پایانی را تولید می کند، رخ دهد.
دو شرط بایستی برای یک متغیر مفید برقرار باشد:

1. متغیر بتواند در یک فرم جمله ای گرامررخ دهد یا به عبارتی در یک رشته قابل اشتقاق از S وجود داشته باشد.
2. اشتقاق یک رشته پایانی از ان متغیر وجود داشته باشد.

به متغیری که در یک فرم جمله ای رخ می دهد، قابل دسترس (reachable) از S گفته می شود.

گراف عبارات

دیاگرام حالت یک آتاماتا با الفبای ∑ را می توان به عنوان یک گراف عبارت در نظر گرفت. برچسب ها شامل لامبدا و عبارات متناظر با عناصر ∑ می باشند. کمانهای یک عبارت می توانند باø نیز برچسب دار شوند. هر مسیر در یک گراف عبارت، یک عبارت با قاعده تولید می کند. زبان یک گراف عبارت اجتماعی از مجموعه های ارائه شده توسط عبارات با قاعده پذیرفته شده است.

گرامرهای وابسته به متن

گرامرهای وابسته به متن یک مرحله میانی بین گرامرهای مستقل از متن و گرامرهای بدون محدودیت می باشند. در این گرامرها، هیچ محدودیتی برای سمت چپ یک قانون وجود ندارد، اما طول سمت راست آن بایستی حداقل به اندازه طول سمت چپ باشد.

فهرست مطالب

• جایگاه درس در رشته کامپیوتر
• فصل اول: ریاضیات مقدماتی
  • نمادگذاری
  • توابع
  • نظریه مجموعه ها
  • استقراء ریاضی
  • قضایا و پیش قضایا
  • گراف ها
• فصل دوم: زبان ها
  • رشته ها و زبانها
  • مشخصات متناهی زبانها
  • عبارات و مجموعه های با قاعده
• فصل سوم : گرامرهای مستقل از متن
  • گرامرها و زبانهای مستقل از متن
  • مثالهایی از گرامرها و زبان ها
  • گرامرهای باقاعده
  • مروری بر گرامرها و زبان ها
• فصل چهارم : مقدمه ای بر پارسر ها
  • اشتقاقهای چپ و ابهام
  • گراف یک گرامر
  • الگوریتم های تجزیه
  • پارسر بالا به پایین سطحی
  • پارسر بالا به پایین عمقی
  • تجزیه پایین به بالا
  • پارسر پایین به بالای عمقی
• فصل پنجم : فرم های نرمال
  • حذف قوانین لامبداء
  • حذف قوانین زنجیره ای
  • عناصر غیر مفید
  • فرم نرمال شومسکی
  • حذف بازگشت چپ مستقیم
  • فرم نرمال گریباش
• فصل ششم : آتاماتای متناهی
  • آتاماتای متناهی قطعی (Finite-State Machine)
  • دیاگرامهای حالت و مثالها
  • آتاماتای متناهی غیر قطعی
  • گذرهای لامبدا
  • حذف غیر قطعیت
• فصل هفتم : زبانها و مجموعه های با قاعده
  • آتاماتای متناهی و مجموعه های با قاعده
  • گراف عبارات
  • گرامرهای باقاعده و آتاماتای متناهی
  • ویژگیهای همبستگی زبانهای باقاعده
  • یک زبان بی قاعده
  • پیش قضیه فشار برای زبانهای باقاعده
• فصل هشتم: آتاماتای Pushdown
  • آتاماتای pushdown
  • انواع PDA
  • آتاماتای pushdown و زبانهای مستقل از متن
  • پیش قضیه فشار برای زبانهای مستقل از متن
  • خصوصیات همبستگی زبانهای مستقل از متن
  • آتاماتای دو پشته ای
• فصل نهم : ماشینهای تورینگ
  • ماشین تورینگ استاندارد
  • ماشین تورینگ به عنوان پذیرنده زبان
  • انواع پذیرش در ماشینهای تورینگ
  • ماشینهای چند شیاره
  • ماشین تورینگ با نوار دو طرفه
  • ماشینهای چند نواره
• فصل دهم: طبقه بندی شومسکی
  • گرامرهای بدون محدودیت
  • گرامرهای وابسته به متن
  • آتاماتای خطی محدود
  • طبقه بندی شومسکی