حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۴۳

زبان A را در نظر بگیرید . (DROP-OUT(A را زبانی در نظر می‌گیریم که شامل همه‌ی رشته هایی است که با حذف یک سمبل از رشته‌ی A به دست می‌آیند . بنابر این داریم { ∑DROP-OUT(A) = { xz | xyz ϵ A where x,z ϵ ∑▒* , y ϵ نشان دهید که کلاس زبان‌های منظم تحت عمل DROP-OUT بسته است ، مانند قضیه‌ی 1.47 استدلال کنید.

پاسخ :

اگر زبانی منظم باشد می‌توان یک DFA مانند M برای آن در نظرگرفت . فرض کنیم رشته‌ی S1 توسط ماشین M پذیرفته شود . رشته‌ی S2 را رشته ای درنظر میگیریم که با حذف یکی از نمادهای رشته‌ی S1 به دست می‌آید . اگر ماشینی بخواهیم که رشته‌ی S2 را بپذیرد کافیست از ماشین M حالتی که برای پذیرفتن آن سمبل بوده است را حذف کنیم و تمام transaction هایی که به آن حالت ختم می‌شده اند را به حالت بعدی آن ختم کنیم . بعد از این کار باید transactionها را update کنیم زیرا مثلا ممکن است حالتی که حذف میشود با نمادی که در حالت DROP-OUT حذف شده است به خودش باز گردد اما در حالت جدید باید به حالت بعدی برود.همچنین اگر نماد حذف شده نماد اول رشته‌ی S1 باشد و باعث حذف حالت آغازی شود باید حالتی که حالت آغازی با سمبل حذف شده به آن می‌رود ، به عنوان حالت آغازی در نظر گرفته شود . به این ترتیب برای هر زبانی که از عمل (DROP-OUT(A حاصل می‌شود می‌توان یک DFA یا NFA درنظر گرفت و زبان منظمی است . در نتیجه کلاس زبان‌های منظم تحت عمل DROP-OUT بسته می‌باشد.