نظریه زبان‌ها و ماشین‌ها

مفاهیم پایه

آتوماتای متناهی

زبان‌های منظم و نامنظم

پذیرنده متناهی غیرقطعی (NFA)

رابطه هم ارزی و کمینه‌سازی DFA

گرامر و انواع گرامر و انواع زبان

عبارات منظم، زبان‌های منظم و خواص آن

زبان‌ها و گرامرهای مستقل از متن

ماشین پشته‌ای

ماشین تورینگ

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

در جلسه هفدهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «ماشین‌تورینگ (1)»، فصل دهم این درس با عنوان «ماشین تورینگ» آغاز می‌شود. 

ماشین‌ تورینگ (1)

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

پیش‌گفتار و مفاهیم پایه

در جلسه دوم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «تکمیل مفاهیم پایه و چند تست مفهومی»، ادامه مفاهیم پایه‌ای لازم برای درک این درس ارائه می‌شود و ده مثال و تست مفهومی نیز مطرح و حل تشریحی آنها با جزئیات کامل ارائه می‌شود.

تکمیل مفاهیم پایه و چند تست مفهومی

در جلسه سوم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «پذیرنده متناهی قطعی (DFA)»، فصل دوم این درس با عنوان «اتوماتای متناهی» آغاز می‌شود. انواع پذیرنده‌های متناهی (FSA) شامل پذیرنده‌ متناهی قطعی یا معین (DFA) و پذیرنده‌ متناهی غیرقطعی (NFA) است. در این جلسه پذیرنده‌ متناهی قطعی یا معین (DFA: Deterministic Finite State Accepter) تعریف شده و  یک مثال در مورد آن زده می‌شود. سپس در مورد اینکه چرا DFA یک ماشین متناهی است صحبت می‌شود. سپس در مورد توصیف DFA با یک گراف جهت‌دار بحث می‌شود. در ادامه مفاهیم لازم برای درک این مطلب ارائه می‌شود و چندین مثال مفهومی نیز مطرح و تشریح می‌شود.

پذیرنده متناهی قطعی (DFA)

در جلسه چهارم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «زبان‌های منظم و ارتباط آن با DFA»، فصل سوم این درس با عنوان «زبان‌های منظم» آغاز می‌شود. ابتدا زبان منظم بر اساس مفهوم DFA تعریف شده و پس از آن 8 مثال در مورد زبان‌های منظم مطرح و حل می‌شود. سپس تعریف دو اتوماتای هم‌ارز مطح می‌گردد. پس از آن DFA یا ماشین کمینه تعریف می‌شود و 6 مثال در مورد آن مطرح و حل تشریحی آن ارائه می‌شود. سپس اصل لانه کبوتری مطرح می‌شود. سپس یک مثال اثباتی مطرح و اثبات آن بر اساس برهان خلف ارائه می‌شود. در ادامه چند مسئله و قضیه در این خصوص مورد بحث قرار می‌گیرند.

زبان‌های منظم و ارتباط آن با DFA

در جلسه پنجم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «ویژگی‌های زبان‌های منظم و نامنظم»، ادامه فصل سوم این درس با عنوان «زبان‌های منظم» تدریس می‌شود. ابتدا DFA زبان L و متمم زبان L تعریف و نحوه استخراج آنها از روی هم تشریح می‌شود. سپس خانواده زبان‌های منظم تحت عمل اشتراک شرح داده می‌شود و قضیه مربوطه با اثبات آن ارائه می‌شود. سپس اثبات می‌شود که اشتراک تعداد متناهی از زبان‌های منظم، منظم است و مثالی در این رابطه حل می‌شود. پس از آن نشان داده می‌شود که متمم یک زبان نامنظم، نامنظم است. پس از آن این پرسش مطرح می‌شود که آیا اشتراک تعداد نامتناهی از زبان‌های منظم، منظم است؟ آنگاه پاسخ منفی این پرسش اثبات می‌شود. سپس این قضیه اثبات می‌شود که اجتماع دو زبان منظم، منظم است. سپس نتیجه گرفته می‌شود که خانواده زبان‌های منظم تحت سه عمل اشتراک، اجتماع و متمم‌گیری بسته هستند، اما تحت دو عمل اجتماع نامتناهی و اشتراک نامتناهی بسته نیستند. سپس چند نکته مهم کنکوری در این رابطه مطرح و شرح داده می‌شود. سپس قضایا و نکات کنکوری و مطالب متعددی مانند بسته بودن خانواده زبان‌های منظم تحت عمل خارج قسمت راست زبان‌ها  و تحت عمل تقسیم راست بر هر زبان دلخواه مورد بحث و بررسی دقیق قرار می‌گیرد. سپس DFA کمینه یا مینیمال مطرح می‌شود. آنگاه به مبحث تصویر همریختی یک زبان منظم پرداخته می‌شود. در انتها یک جمع‌بندی از زبان‌های نامنظم ارائه می‌گردد.

تعریف می‌شود و 6 مثال در مورد آن مطرح و حل تشریحی آن ارائه می‌شود. سپس اصل لانه کبوتری مطرح می‌شود. سپس یک مثال اثباتی مطرح و اثبات آن بر اساس برهان خلف ارائه می‌شود. در ادامه چند مسئله و قضیه در این خصوص مورد بحث قرار می‌گیرند.

ویژگی‌های زبان‌های منظم و نامنظم

در جلسه ششم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «پذیرنده متناهی غیرقطعی (NFA)»، فصل چهارم این درس تدریس می‌شود. ابتدا پذیرنده‌ متناهی غیر قطعی یا نامعین (NFA: Nondeterministic Finite Accepter ) تعریف و تشریح می‌شود. سپس نشان داده می‌شود که NFA یک ماشین غیر قطعی یا نامعین است. سپس چندین مثال به همراه نکات متعدد کنکوری و تعاریف مهم و قضایا و لم های مختلف با اثبات و ارائه نتایج آنها برای حل تست‌های کنکور مفصلاً شرح داده می‌شود.

در جلسه هفتم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «رابطه هم ارزی و کمینه‌سازی DFA»، فصل پنجم این درس تدریس می‌شود. ابتدا تعریف دو اتاماتای هم‌ارز ارائه می‌شود. سپس یک DFA کمینه تعریف می‌شود. سپس رابطه هم‌ارزی و کلاس‌های هم‌ارزی دقیقا تعریف شده و بعد از آن وضعیت های ادغام‌پذیر شرح داده می‌شوند. سپس روال علامت‌گذاری تدریس می‌شود. آنگاه وارد مبحث کمینه‌سازی DFA شده و روال دقیق آن به همراه نکات متعدد کنکوری با دو مثال و نیز یک تست و حل تشریحی آن ارائه می‌شود.

رابطه هم ارزی، کلاس‌های هم‌ارزی و کمینه‌سازی DFA‌

در جلسه هشتم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «گرامرهای نوع 0 تا 3 و انواع زبان‌»، فصل ششم این درس آغاز می‌شود. ابتدا تعریف یک گرامر ارائه می‌شود. سپس بیان می‌شود که انواع گرامر با قوانین تولید آنها مشخص می‌شوند. سپس گرامر نوع 0 (بدون محدودیت) تعریف می‌شود. در ادامه گرامر نوع 1 (حساس به متن یا وابسته به متن یا Context Sensitive Grammar) تعریف می‌شود. آنگاه گرامر نوع 2 (مستقل از متن یا  Context Free Grammar) تعریف می‌شود. بعد از آن گرامر نوع 3 (منظم یا Regular Grammar) تعریف می‌شود. پس از آن چند نکته و 5 مثال در خصوص انواع گرامر مطرح و حل تشریحی آن ارائه می‌شود. سپس مفهوم رشته پذیرفته شده توسط گرامر شرح داده می‌شود و به دنبال آن زبان گرامر تعریف و یک مثال برای تعیین زبان گرامر زده می‌شود.سپس انواع زبانها شامل زبان نوع 0 (بدون محدودیت)، زبان نوع 1 (حساس به متن یا وابسته به متن یا Context Sensitive Language)، زبان نوع 2 (مستقل از متن یا  Context Free Language) و زبان منظم یا Regular Language تعریف می‌شود. گرامر خطی و زبان خطی نیز تعریف می‌گردد. سپس ربط بین گرامر خطی راست و زبان‌های منظم شرح داده می‌شود. در انتها نکات مربوطه و قضایای آن با اثبات و به همراه مثال‌های مربوطه پایان بخش مطالب مهم این جلسه است.

گرامرهای نوع 0 تا 3 و انواع زبان‌

در جلسه نهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «طراحی گرامرها و گرامرهای منظم و خطی»، ادامه فصل ششم این درس تدریس می‌شود. ابتدا مبحث طراحی گرامر برای زبان دلخواه ارائه می‌شود. سپس 15 مثال کامل برای این مطلب مطرح و حل تشریحی آن ارائه می‌گردد. سپس نکات و ویژگی های زبان های منظم و مباحث مربوط به گرامرهای خطی راست و چپ و NFA و  DFA مطرح می‌شود. در همه موارد مثال‌های روشنگر برای درک مطالب زده می‌شود.

طراحی گرامرها و گرامرهای منظم و خطی

در جلسه دهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «عبارت‌های منظم، زبان‌های منظم و گراف انتقال تعمیم‌یافته»، فصل هفتم این درس آغاز می‌شود. در این رابطه چندین قضیه و  تعاریف و نکات مربوطه با مثال‌های متعدد شرح داده می‌شود.

عبارت‌های منظم، زبان‌های منظم و گراف انتقال تعمیم‌یافته

در جلسه یازدهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «خواص بستاری زبان‌های منظم»، ادامه فصل هفتم این درس تدریس می‌شود. در این رابطه چندین قضیه و  تعاریف و نکات مربوطه با مثال‌های متعدد شرح داده می‌شود.

خواص بستاری زبان‌های منظم

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

نمایش استاندارد زبان‌های منظم و زبان‌ها و گرامرهای مستقل از متن 

در جلسه سیزدهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «اشتقاق در گرامرهای مستقل از متن»، ادامه فصل هشتم این درس تدریس می‌شود. در این جلسه مطالب مربوط به مفاهیم اشتقاق چپ و راست و ویژگی‌های آنها و درخت اشتقاق و نکات مربوطه در گرامرهای مستقل از متن با مثال شرح داده و تکمیل می‌شود.

اشتقاق در گرامرهای مستقل از متن

در جلسه چهاردهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «گرامرهای مستقل از متن، ساده، گنگ، ساده‌سازی و فرم های نرمال»، ادامه فصل هشتم این درس تدریس می‌شود. 

گرامرهای مستقل از متن، ساده، گنگ، ساده‌سازی و فرم های نرمال

در جلسه پانزدهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «ماشین‌های پشته‌ای قطعی و غیرقطعی»، فصل نهم این درس با عنوان «ماشین پشته‌ای» تدریس می‌شود. 

ماشین‌های پشته‌ای قطعی و غیرقطعی

در جلسه شانزدهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «ماشین‌های پشته‌ای و زبان‌‌های مستقل از متن»، دومین جلسه از فصل نهم این درس با عنوان «ماشین پشته‌ای» تدریس می‌شود. 

ماشین‌های پشته‌ای و زبان‌‌های مستقل از متن

در جلسه هجدهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «خواص بستاری زبان‌های مستقل از متن و ماشین تورینگ (2)»، ادامه فصل دهم این درس با عنوان «ماشین تورینگ» تدریس می‌شود. 

خواص بستاری زبان‌های مستقل از متن و ماشین تورینگ (2)

در جلسه نوزدهم درس نظریه زبان‌ها و ماشین‌های دکتر حمید سیدجوادی که از دروس مهم کنکور ارشد مهندسی کامپیوتر است، با عنوان «خواص تعمیم‌پذیری زبان‌های مستقل از متن»، آخرین بخش از فصل دهم این درس با عنوان «ماشین تورینگ» تدریس می‌شود. 

خواص تعمیم‌پذیری زبان‌های مستقل از متن

دکتر حمید سیدجوادی

فیلم آموزشی سیستم عامل کنکور ارشد | جزوه سیستم عامل کنکور کامپیوتر | دکتر حقیقت | نکته و تست سیستم عامل

سیستم عامل

فیلم آموزشی شبکه های کامپیوتری کنکور ارشد | جزوه شبکه های کامپیوتری کنکور کامپیوتر | دکتر حقیقت | نکته و تست شبکه های کامپیوتری

شبکه های کامپیوتری

فیلم آموزشی پایگاه داده کنکور ارشد | جزوه پایگاه داده کنکور کامپیوتر | دکتر کیوانپور | نکته و تست پایگاه داده

پایگاه داده

فیلم آموزشی ریاضی گسسته کنکور ارشد | جزوه ریاضی گسسته کنکور کامپیوتر | دکتر کاشفی | دکتر سیدجوادی | نکته و تست ریاضی گسسته

ریاضی گسسته

فیلم آموزشی ساختمان داده کنکور ارشد | جزوه ساختمان داده کنکور کامپیوتر | استاد طورانی | نکته و تست ساختمان داده

ساختمان داده

فیلم آموزشی طراحی الگوریتم کنکور ارشد | جزوه طراحی الگوریتم کنکور کامپیوتر | استاد انصاری | دکتر سیدجوادی | نکته و تست طراحی الگوریتم

طراحی الگوریتم

فیلم آموزشی هوش مصنوعی کنکور ارشد | جزوه هوش مصنوعی کنکور کامپیوتر | استاد انصاری | نکته و تست هوش مصنوعی

هوش مصنوعی

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