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

ثابت کنید زبان های زیر منظم نیستند. شما می توانید از لم تزریق و بستار کلاس زبان های منظم تحت اجتماع, اشتراک و مکمل استفاده کنید.

الف) با استفاده از لم تزریق و انتخاب s = 0p10p = xyz اینکار را انجام می دهیم. اینجا xy فقط شامل 0 است. فرض میکنیمY = 0k و K > 0 است. پس

xy0z = 0p–k10p .  در زبان نیست. پس منظم نیست.

ج) فرض کنید L = {w | w in {0,1}* is a palindrome} مکمل زبان باشد. s را s = 0p10p = xyz انتخاب می کنیم که در L متقارن است. اینجا xy فقط شامل 0 است. فرض کنید k>0y = 0k , k>0. بنابرین xy0z = 0p–k10p متقارن نیست پس در زبان نیست . پس L متقارن نیست.

د) با استفاده از لم تزریق و انتخاب s = 0p10p = xyz اینکار را انجام می دهیم.اینجا xy فقط شامل 0 است. فرض کنیدy = 0k,y = 0k باشد.بنابرین

xy0z = 0p–k10p در زبان نیست. پس L متقارن نیست.