توضیحات

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