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

تمرین

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

حل

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