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

حل تمرین1-37

تمرین

Show that the language F={w|w is not a palindrome}satisfies the three conditions of the pumping lemma even though it is not regular.Explain why this fact does not contradict the pumping lemma!

نشان دهید که {قرینه نیست F={w|w اگرچه نامنظم است سه شرط لم تزریق را ارضا می کند. توضیح دهید چرا با لم تزریق تناقض ندارد.

• این سوال غلط می باشد

می توان نشان داد که این زبان لم تزریق ندارد

ولی زبانهای دیگری وجود دارند که منظم نیستند ولی لم تزریق دارند

حل

نشان می دهیم که لم تزریق ندارد.

لم تزریق را مورد بررسی قرار میدهیم:

با فرض عدد P (طول تزریق) داریم:

S=xyz , |S|>=P

S = a^p!.b.a^p!+p

=> y = a^k , 1<k<p

xyyⁱz = a^p+k .b.a^p+1 لم تزریق دارد

i = 0 xz = a^p-k.b.a^p+1

داریم:

S = a^p+ik.b.b.a^p!+p | => y = a^k , 1<k<p i = p! / k

عضو زبان نیست این تناقض است.

این زبان لم تزریق ندارد پس نامنظم است.