حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۱۷

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

تمرین[ویرایش]

الف) فرض کنید که C یک زبان مستقل از متن و R یک زبان منظم باشند.ثابت کنید که زبان C اشتراک R مستقل
از متن است؟
ب) با استفاده از قسمت الف نشان دهید که زبان زیر مستقل از متن نیست.
{ W | رشته W عضو *{c,b,a} بوده و دارای تعداد مساوی از aو bو c است }

حل[ویرایش]

الف) (؟)
ب) فرض می کنیم مستقل از متن است (فرض خلف) می‌دانیم زبانی که دارای رشته‌های *a*b*c است، منظم است
بنابراین طبق الف بایداشتراک آن ها یعنی anbncn مستقل از متن باشد که می‌دانیم اینگونه نیست.پس به تناقض می رسیم. پس زبان مذکور مستقل از متن نیست.