حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-23

حل تمرین 1-23

تمرین

ثابت کنید زبان های زیر منظم نیستند:

پ) { 0^m 1^n | m=!n }

ت) { رشته w دو طرفه نباشد. {0,1}€w | w }

حل

پ)ما می دانیم که:

{0n1n | n >= 0} = {0m1n | m,n >= 0}^{0*1*}c

هنگامی از ^ استفاده می کنمیم که بخواهیم فصل مشترکی داشته باشیم.میبایست از برهان خلف استفاده کرد.

اگر {0m1n | m is not equal to n} باشد که برقرار است سپس {0n1n | n >= 0} قطعاً برقرار است چونکه 0*1 برقرار است بخاطر اینکه خاصیت بسته بودن بر قرار می‌باشد.

////////////////////////////////////////////////////////////////////////

ت)http://209.85.229.132/search?q=cache:zQhqM6V0ByoJ:www-cse.ucsd.edu/classes/su04/cse105/ss1.ps+d.+Proof+by+contradiction.+Assume+that+the+language+L+%3D+%7Bw%7Cw+is+not+a+palindrome+%7D&cd=4&hl=en&ct=clnk edited by Mohamad Hasan Doustari